Your kinda screwed. A lot of the big providers (and small) use blocklists garnered from a bunch of companies who may or may not be responsive - and more often than not simply dont care about the small guy... amongst those companies ive had the most grief with SORBS for my various clients. Some lists you can get off of, others are essentially impossible... amongst which are the "Dynamic IP" and "home user" lists.
When people set up which block lists to use, there are a couple that are not for specific offenders, but are instead simply full lists of all the known IPs in an ISP's block - such as all DSL / cable modem users. the thought being that you can block all email originating from peoples home connections, etc... which is under the presumption that legitimate emails will never come from cheap consumer grade connections which to be fair are largely spam. Problem is there are tons of small businesses with essentially "home" connections... even under business accounts they get lumped into the same IP ranges.
The real issue is that in the last few years - particularly since gmail came about... email itself has begun to concentrate in only a few major providers hands... namely intermedia, office365 and gmail. As less and less small/medium sized businesses have their own mail servers the big boys have less concern for keeping things more flexibly acceptable - very few outfits have their own exchange servers anymore, i dropped my last internally maintained client mail server a few years ago, even bigger companies dont want to run exchange in house anymore - its just not worth it in most situations that dont have regulatory or legal requirements. The less companies that run their own mail servers the greater the liklihood that legitimate mail will only come from the major providers (and the less likely wholesale blocking of IP's is going to cause the sales team to freak out when their clients arent getting emails - which is honestly the only way ive ever seen IT departments actually lower their filter strength - usually after being yelled at by the sales execs).
In order to deal with this problem we have found the best lasting solution is to use a store and forward relay service such as spamstopshere or setup your own via a micro instance in amazon. Postifx and Mailenable (windows) are two great programs that do the trick quite well. By setting up your own instance with a public IP which is more "trsuted" (comming from a major source of servers which have other large mail hosts running in the same IP block) you avoid all sorts of problems... you will have to do the normal MX, SPF and rDNS things as well for full compliance.
In general this is better anyways, as you probably also want an inbound store and forward for those outages you memntioned (no lost emails!), and youll get the probably unneeded benefit of masking your real world address (one of my clients got a detailed direct bomb threat from a guy who found their address using an IP lookup - their address was otherwise unlisted).
a micro instance on amazon is VERY cheap, and can be used for other things - like a simple website, a connection monitor etc..
good luck
