This site has pretty much every country as a vector map. You can use them for free (under creative commons [attribution]), or if you want to use them commercially they're pretty cheap.
Last edited by Rythal; 01-04-2014 at 01:59 AM. Reason: clarified that it is a Creative Commons ATTRIBUTION liscence
Pretty sure it is.Creative Commons Attribution License: Please provide the following note and link on your website or design: "Map of Canada with Provinces - Single Color by FreeVectorMaps.com"
Ah, I was looking at the paid license, which, rather strangely, seems to be WAY more restrictive than the CC license they provide for free.
Still, I'd go for Natural Earth instead. It's public domain and maintains its georeferencing and attributes to it can be easily reprojected and re-symbolized.