I've only ever seen this in Ubuntu for some reason and it is because of the /etc/nsswitch.conf settings.
So the issue is that if the hostname's reverse DNS cannot be found that you need to go back to DNS which was not the default in this nsswitch.conf file for some strange reason.
Edit /etc/nsswitch.conf and replace your "hosts" line with this:
#hosts: files dns mdns4_minimal [NOTFOUND=return] mdns4
hosts: files mdns4_minimal [NOTFOUND=return] dns [NOTFOUND=return] mdns4
I kept the original hosts line commented out in case I need to return to the original although I doubt it.
After editing like above then ping responds right away without a several second delay.