Is it possible that your server is using IPv6 and that your DNS for IPv6 is not setup correctly? It has to be setup in both directions so doing DNS of the hostname returns the same IP that google sees and reverse DNS of the IP address (v6 or v4 I assume) shows the hostname.