Like many others it seems, I've recently started getting mail sent to Virgin Media users rejected. I'm actually a Virgin Media customer myself, although don't regularly use my Virgin mailbox. I have accounts on my own Exchange server and with external providers though, with mails sent from both being rejected.
I was able to e-mail the same user just a few weeks ago. I can obviously provide more detail of the mails themselves, but would rather do that on request rather than having to post that in a public forum.