Also super annoying when switching countries. The lack of an international prefix on your existing contacts means they are now unontactable, and all your existing chats show as unsaved contacts with an international prefix.
I think the obvious solution here is to store your contacts with the country code. I believe you can also append it to contacts after the fact and it will update the iMessage thread. If you travel or have contacts out of your country, I find this to be useful.
Any idea if it's possible to prepend it to contacts in bulk?