That’s not quite accurate – at least not from the discussions I’ve had with MessageLabs. My domain and addresses aren’t on any blacklists that I can see.
The problem I have is that I email a company, it rejects, then I have to contact them via another email address and then somehow convince the person I’m emailing to talk to their IT department, then I have to convince that IT department that my messages aren’t problematic. It’s time consuming and annoying. In some cases, the IT department (quite rightly) refuse to adjust their filters for me.
MessageLabs now appear to be looking into this.