Who is your host? I’ve read many, many complaints about this type of thing and, sadly, I don’t think there is much that can be done by hosts because of the way the spam marking and blacklisting process works. I think it is downright stupid to block an entire IP address because of alleged spam. And by alleged, I mean that some email providers allow customers to flag emails as spam even if they are not spam, such as someone who subscribes to an email newsletter and instead of unsubscribing hits the spam button which can lead to the provider blacklisting the IP address. You will read a lot of complaints about AOL doing this and they are not the only one.
No, I would not say it is incompetence on the part of the host. I would say it is the fault of email providers for resorting to a knee-jerk reaction of blacklisting entire IP addresses regardless of the actual sender of the alleged spam and not taking the time to determine if something is actually spam. If the IP is blacklisted, I don’t suppose something like an SPF record or [URL=“http://en.wikipedia.org/wiki/DomainKeys_Identified_Mail”]DomainKeys (DKIM) would help in that case, would it?
Some hosts offer dedicated IP addresses for a cost of $2 a month or so. Maybe you could look into that.