Is this a Virtuozzo VPS? If so, resolv.conf gets re-written by the host node. You would need to contact your VPS hosting provider to stop this happening/get them to add localhost to your DNS servers.

Having said that we are a VPS Hosting provider and use Virtuozzo and this is not an issue on our own internal VPSes. Unfortunately, for the life of me I can't remember what I did - if anything - to stop resolv.conf being changed by the host.

They tell me it's VirtualBox but the power panel interface is Virtuozzo. Not sure how to answer the question

Wait, I'm confusing different boxen. This one is not virtual at all. Just a real live server with Plesk on it.

Ah. OK. Well, this won't help then, but just for completeness the way to get Virtuozzo to not overwrite resolv.conf is to not set any DNS servers for the Container on the host node (this has to be done by the host node administrator - it can't be done via the Power Panel or the Container itself)