I don't know a lot about this, to be honest. I am originally Swedish, and the Swedish passport has the most visa-waivers in the world, so it's not a topic I had much personal interest in. I know about Mexico for sure, and I've heard that other non-first world countries do it as well.
You can find more information at the website of the Mexican embassy in Ottawa at http://www.sre.gob.mx/canadaingles/ - click on Consular Services and then Visa Information. This is the information from their site, current as of today:
"Landed Immigrants of Canada
The Embassy of Mexico in Canada informs that starting on December 1, 2003, landed immigrants of Canada do not require a visa. However, they do need a tourist card, which may be obtained at Mexican consulates, on direct flights to Mexico or at the Mexican airport, and they must travel with the following:
*
Valid passport
*
Permanent resident ID card
*
Round trip tickets
*
Proof of economic solvency (credit card, traveller's cheques, etc.)
Please be aware that foreigners visiting Mexico must pay a tax fee (derecho de no inmigrante). When travelling by plane, the US$20.00 fee is included in the airplane ticket. When travelling by car, this tax will be charged at the port of entry."