Agree - the really big providers are pretty good because you can get in contact with somebody who gives a shit at the other end and can fix things up. They do so much volume that they can afford somebody who cares about it.

The really painful things are either places that subscribe to dodgy blocklists and never check their configuration, or... yeah, places like t-online.de and free.fr.