The solution provided by @SteveZz87 worked for me. I use a Jabber account with a specific server, so I had to tweak it a little more.
Below details composed my keychain at first:
Name: com.apple.account.jabber.password
Kind: application password
Account: email@company.com@server.com
Where: com.apple.account.jabber.password
Then I updated it with below details:
Name: com.apple.account.Jabber.password
Kind: application password
Account: email@company.com
Where: Jabber
Then I restart Messages, and after asking me twice for my keychain password, it worked. We tried the same trick with a friend, but he was unable to change the "Where" value to "Jabber". We searched for all items with the keyword "Jabber" (found 5) and deleted all of them until we ended up with just one with the above update, it worked.