Yes, that seems the most likely cause. If you have other prints from the same lab that do match your screen, and if you're still safely in sRGB, there's no reason why this batch shouldn't have matched too.
Even by the standards of eleven years ago, 1.5 megapixels was oddly small. Are you sure you have the exact file that came out of the camera? Not a copy that's been shrunk by an email program, perhaps?
If they really do stretch it, then it means you have to leave them some area to stretch. Eg give them an inch to stretch into two inches. But if you don't know exactly how much to allow, then all your questions about sizing and sharpening are completely moot.
DON'T trust them with this important task. Do it yourself.
Great! So what's the problem?? Just close your logo PSD file, and never open it again.
When you need to use it on a photo, go to File>Place, exactly as my instructions say.