I tried to look back and get it right, I am out of the loop now with everyone's names. Yes, the constancia is at the PGR in Mexico City, only. My partner did not live in Mexico City after he turned 18 so we sent only the state police checks, initially. They did end up requesting a police check from Mexico City (this does not actually exist in itself) along with the request for the constancia. My partner arrived in Canada 2 days before the visitor visa became a requirement for Mexicans. We decided the chance of him getting a visitor visa was too low and I didn't let him leave Canada for 2 years, just in case. It will be a lot easier with a multiple entry visa, it will provide you the freedom to go back and forth as needed.
I think Islenio got the constancia through the Mexican embassy in Canada? Here is the link anyway:
http://embamex.sre.gob.mx/canada/index.php?option=com_content&view=article&id=169&Itemid=41
One thing that I can remember is the instruction page the Canadian embassy sends you to get the constancia does not mention fingerprints, it assumes that you are physically present in Mexico to get them done at the PGR. So if you send someone to the PGR for the constancia don't foget to send them your fingerprints, too (3 sets)!