I ran into this today and wanted to share my fix, since this one is simply overlooked and easy to fix.
We manage our own rDNS and recently redid our server naming scheme. As part of that, we should have updated our rDNS and forgot to do this.
A ping turned up the correct hostname, but a ping -a returned the wrong hostname.
Easy fix: change the rDNS, do an ipconfig /flushdns, wait 30 seconds (just something I do), do another ping -a , see it resolving the correct hostname, connect ... profit.