The only other game in town that I know of is Worldband (http://www.worldband.com/). I know somebody who has a couple of static addresses and pays a lot less than mentioned above per month, but I'm not sure whether that's generally available. (Also, Worldband seems to not advertise to end users at all, but will happily provide them net. Their customer service is awesome.) I say "the only game in town" unless you've actually found a way to get multiple static addresses from Verizon, which I didn't think was possible without a rather pricey business-oriented plan.

We have the medium Verizon DSL plan, 3Mb/s down and 768kb/s up, $30 a month. As far as the actual movement of bits goes, it's great. I don't use their mail servers at all, though; all they see are a lot of encrypted bits going back and forth, and they don't seem to mind. There have been a handful of late-night maintenance windows (over years of service) where service dropped for a few minutes, but it's far from frequent enough that I've thought about setting something up to automatically restart pppd. Also one actual "something broke" outage which was well-documented on their service status site and fixed within a few hours.

Why the need for static addresses? Any chance having a colo box somewhere else (real or virtual) will give you what you need?