How difficult that would be for you? How many countries we are talking about? I had issues getting FBI clearance as they were asking for my 65 yrs old mother who never lived in the USA for 6 months at a time, but CIC looks at cumulative 6 months.
Only if it's
extremely hard, I would approach local embassies and/or get screenshot from their embassy/police website that they don't provide such service for whatever reason (due to not having valid status in that country anymore or they don't service foreigners).
CIC has option for such cases but personally I would use this as last resort (right before giving up)
http://www.cic.gc.ca/english/helpcentre/answer.asp?qnum=035&top=4