While trying to diagnose another issue, I've just found that my servers hostname pings as I tried this both from my own computer and from a website which finds the IP address of a server.

I fixed it using the 'Add an A Entry for your Hostname' in WHM (even though this had been done before) so it's fine now.

But how was this even possible?