I am now on the SORBS-SPAM blacklist, how can I get myself removed?
This was an issue originally with another machine in our company which has since been cleaned up, but I think because I share the same domain name I am being blocked.
You may want to look at the blacklisting site in question and see if there's a link with instructions how to get removed. Most do have some instructions, but don't think they'll be friendly about it...they routinely deal with spammers and angry people, so you'll have to work extra hard to keep your patience level high and be as understanding as possible.
Being friendly (if their procedure isn't automated, which it may be) if you find that you're dealing with a human at some point can get you further than losing your patience with them.