How do I delete contact suggestions from Messages in OS X?
The answer provided by @Noldorin works for me: 


  Messages on OS X doesn't allow "Recent" contacts to be deleted, but
  Messages on iOS does allow this. An oversight by Apple, but this is a
  fix nonetheless.


To clarify, I looked at recent addresses on my iPhone/iMessage when starting a new conversation. There's an "i" symbol which allows your to see recent group conversations and addresses, and also a remove button.

Once removed the erroneous address is no longer visible in OS X iMessage.