Did you check them before paying? If not, I'd say you were not doing your job. That is step 1 before signing any contracts for internet service - check to so if the IP space you are getting has a bad net rep! See if you can find out who had it last, etc. You could wind up with even worse than mail blacklisting if you don't! For instance there have been cases of providers selling hijacked IP blocks that were not theirs to sell in the first place, etc.
As a mail server operator, it is my right to block anyone that our organization decides should blocked. Spammy ISP's fall into that category here in some cases.
Even tier one providors can wind up on lists if they ignore enough LARTs
Sounds like your problem is with qwest for selling you IPs with a bad reputation.
Nice to hear the system is working as it should.
You should be pissed at QWEST that you had to do this. They had to have known the space was listed. It does not get listed (in most lists anyway) without them being notified that there is a problem.
Yes. And the ISP should know better than to lease them out without either warning the customer or havoing them cleaned up first.
Good for you. I use a mix of both. Guess which tends to be more accurate (less false postives, more actual spam filtered)?....... yup, the lists. Hands down.