I was hoping to find out why this might be happening. Everything suggests that it is a bug in iMessage, or "Messages". When I view the certificate it is valid for *.
google.com which means there is no reason it shouldn't be accepted *unless* there is something wrong with the authority chain, but even there, I can't see anything. Oddly, when this comes up, it isn't consistent as to which of how many accounts it gets. *rarely* does it affect all accounts. Today it was just one account.
So far, I haven't found anyone suggest anything other than workarounds. Though one may be less of a workaround than actually it should be. "Do not discover service" or smething like that.