I've just been researching the same problem myself, and came accross a program called SMTPfeed. Don't know anything more about it, except for a mailer comparison page which claimed that it was one of the better high volume mail thingies. Supposedly plugs into sendmail somehow, so you won't have to abandon your setup.
It's a Debian package in the current distro so you should be able to apt-get it. Let me know if you try it because I have to do the same in a few weeks.