I was having the same problem and I figured it out (although it's a bit of a long fix). If you go into your Contacts app on your Mac on the left column you'll see the options All Contacts, iCloud, etc. You'll notice that the contacts that don't show up properly in Messages will turn up under "All Contacts" but not under "iCloud". So, pull up the contact that won't display properly in Messages using "All Contacts" and drag it onto "iCloud". This'll merge it with your iCloud-saved contacts database. Now if you quit Messages and go back in it may fix the problem. If not, there's one additional step that I had to take with some of my contacts. In the "To" field at the top of the message where you see the phone number show up, you'll find a little pull-down menu. Click on it and it'll give you some options, one of which is "Add to existing account". Choose that, scroll down to the proper contact and select it.
I know this is an annoying process, but I went through all of them and everything's good now on my end.