I send quite a lot of email for work and other things and I have what I think is a higher-than-average number of email addresses to manage.
One adjustment I made - I now archive older emails to avoid extra storage costs, which in turn means that searching for older emails is slightly more hassle.
Fastmail's web interface and mobile app are not quite as slick (as gmail) but this isn't a big deal for me personally.
I have also taken the time to run my own calendar and contact services.
For mail, I run Postfix and Dovecot over SSL and access email from my iPhone or web browser using Squirrelmail.
For contacts and calendar I use Baikal.
Yikes.
Isn't this exactly the problem with running your own email setup? And have you not found that keeping on the white side of mail server lists is a constant and moving target?
May I ask, do you send a lot of mail and have multiple accounts? (I do, so this overhead would be impossible for me to manage personally)