are you sure you don't have an open relay? I'm not questioning your abilities, but maybe someone set up a relay on your network that you don't know about? how controlled is your network?

anyway, I have known a few sites that have been blacklisted and depending on the group that blackholed you it can be anywhere from a simple email to the admin explaining that you aren't an open relay to downright impossible to be removed.

The folks over at www.somethingawful.com got put on a blacklist because of a spammer that happened to be in the same IP block as them. The whole block was blacklisted and now SA has been perma-listed because they argued with the admins that they should not have been blacklisted in the first place.

anyway, drop 'em a line or call them if they aren't even receiving your emails any more. good luck, and let us know what happens.