On not public server: Host name example.com could not be resolved: Name or service not known This is not a duplicate (please read carefully)

Digging in mysql logs of a production server I found a few entries with the error above, all pointing to the same host name. Each entry appears ~30 seconds right after mysql starts. There is also no record of the hostname in mysql.user table

I would not be surprised if mysql was exposed to public internet but it is not. The port is blocked by lfd/iptables and explicitly allowed for a few public/private IP addresses.

MySQL's skip_name_resolve is not enabled, since I need hostname resolution for a few VPN servers.

Where these entries may be coming from? The server is WHM/CPanel, MySQL 5.6.21
When --skip-name-resolve isn't in specified, the IP address of incoming connections is resolved into a name via a DNS query... 

However, there isn't just one DNS query, because the existence of a reverse DNS entry (e.g. a PTR record 203.0.113.113 &rarr; foo.example.com) is not sufficient for hostname-based authentication -- anybody could change a reverse DNS entry to claim to be any hostname they wanted.  

So there's a second query that occurs.  

Once the hostname is resolved, there's an additional DNS lookup in the opposite direction, to verify that the hostname discovered in the first DNS query, foo.example.com, does indeed map to an A record that resolves back to the original IP address (e.g an A record foo.example.com &rarr; 203.0.113.113).

In this case, the IP address mapped to a hostname, but the hostname did not map back to the original IP address.  

http://dev.mysql.com/doc/refman/5.6/en/host-cache.html