There are deeefinately M. religiosa across the Canadian boarder :] But they're not considered native, since they were brought over from across the pond. And, you'll only find them in the warmer areas. I found mine on a giant island in the middle of Lake Huron (large bodies of water endeavor to equalize seasonal temperatures, etc--which probably prevents the ooths from dying in the winter). Whether they are considered "invasive" or not, I'm unsure--but that'd explain it if they're an illegal species to own/import in canada.
And yeah, Tenoderas don't survive the canadian winters, but as SkittishMale said, the ooths are certainly sold in any big store with a gardening section, and so it's possible to find them around, outside of people's garden, in late summer. At least, there've been folks who have. I'm not surprised though, to hear that you can't just go out to any field away from urban environments, and expect to find some like you would in many parts of the states...
Litaneutria minor is the only mantis species that wasn't brought over from another country. And their population is apparently restricted to the Okanagan valley in B.C.
Canada is such a desert when it comes to mantids U_________U