This appears to be a similar problem to mine Barry....
I am using your nameservers too Adminstrator....
I can see sites on my VPS but when I ping the nameservers I get 'host not found'
I too am on Virgin....I contacted them...got similar reply to you...all appears well from their end.
I can get a response by pinging sites but NOT the nameservers.
Ive rebooted my modem, router, used command prompt to flush dns..you name it, Ive done it...nothing makes a difference.
Happily your problem is solved Im glad to see

whereas mine is still the same as it was yesterday.
Oh and just JFI I have a client who cant see her sites, I can, she is in Netherlands, I am UK so the ISP issue wouldnt apply in my case.
I also have a friend in USA who cant see my site either.....
MaryT