The medical exams are mailed to Trinidad. I did mine about a week before I mailed my application, however I do believe that "when" you do it, is largely irrelevant, as the only purpose of the medical exam is to verify that you don't pose a danger to Canadians. Also, the medical, along with your passport will largely determine the time limit for you to travel to Canada.
What does that mean? That your landing papers can't have a limit date longer than 1 year after you had your medical exams done.
For Example: You do your medicals today, 25 March 2012, and your whole immigration process takes, lets say 8 months, so you get your visa sometime around December. Your Landing Papers will specify that you have to land BEFORE 25 March 2013, as the medical exam is only valid for a year. Unless your passport expired sooner than your medicals, then you'd have less time. Get it?
I had my medical exam done way back in August 2009, which means that the embassy will require me to renew it. It doesn't bother me (that much) to pay for it; last time I paid $275 US Dollars in Tijuana, but they only have one designated medical practitioner for the whole region up there. Here in Mexico City they have tons, so I'm wondering if they overcharged me. What bothers me is time, I hope these guys could just send me in one letter all the things I need, I'd hate it if they ask for the Carta de Antecedentes registorialers or whatever it's called, and then once I hand it in, they take another 2 months to ask for the Medical Exam. Oh well, hopefully I get some news within the next few weeks.