For me it was related to the country code as others have suggested. I can replicate the problem back and forth too. The thing is, it seems to be totally random in terms of which numbers have the issue.
I'm in Canada so it's +1. I have a contact that I message often and her number is saved in iCloud as (403) xxx. In the Messages app on my Macbook she shows up as +1 (403) xxx.
The second I add +1 to the start of her number her name shows up in Messages. When I remove it in iCloud, Messages just shows her number again, starting with +1. Very strange.
To make things more strange, I don't add+1 to any local numbers that I save so almost all of my contacts should have this issue, right? Why is it just her and a handful of others that this applies to? Why does Messages see +1 in front of her number when Contacts on my Macbook, iCloud and iPhone all show her without it?
Very strange indeed. At least I know how to fix it now, it was driving me crazy!