Hi. I've been trying to fix this problem myself for the past 6 months, and the thing that finally did the trick for me was to just reset my keychain.
To do this:
1. Open up KEYCHAIN ACCESS > Preferences
2. Under GENERAL, click "RESET MY DEFAULT KEYCHAIN"
Do keep in mind that this does reset all of your other keychains I believe, but you can just re-input those I think. Plus the originals aren't deleted.
Hopefully this works for you too. Do keep in mind however that I did this on a whim. I was having login issues with Facetime as well, so that led to the assumption that this issue didn't stem from Messages, but rather there was something wrong with my keychain.