[APS]

FYI the normal reason an email server gets on a blacklist is because one of the users who is using it has sent a load of SPAM, either intentionally or unintentionally (their computer has an infection). By either automatic means (using "honeypot" email accounts) or just by receiving customer reports the person/company running the blacklist can add any IP to their list without reference or informing the owner of the email server.

This is one of the problems with using a shared email service. However even if you run your own email server you can still get on a blacklist either because some blacklisting companies will tar a whole bank of IPs from same supplier as a problem if they detect spam coming from one or more in that bank or just by an error in their system (some do not vet the customer complaints too closely).

Companies that provide paid for mail filtering (in and out) tend to be more proactive in getting themselves off blacklists, but they also are more stringent in controlling who sends email through them and how it is sent.

Since switching out company to Postini for mail filtering we have never had a problem with blacklisting, whilst we did have problems before when using general ISP mail severs. Ironically Postini, now part of Google, is used by Virginmedia for SPAM filtering, but I guess as you are not paying extra for a premium version of that service they do not monitor outgoing emails to closely to detect blacklist bounces.

The email address your saw in the bounce must have been in an email generated by VM outgoing server, which was reported the other end had rejected the email. Somewhere in that message or the headers you should have been able to see email server it was going to, or if you wanted to complain again you could try emailing postmaster@ the domain of the person you are trying to send the email to.