Google App Engine would be ideal for this. You don't have to move your entire application to it either, just create a web service that you pump email into and secure it so no-one else can relay. They don't provide a smtp or mail-based interface but you get the benefit of running it on google's scalable infrastructure and a generous free allowance so that you can test it quite robustly for free.
You will have to create a client that connects to the web service and triggers the emails in batches to get around their 30 second page lifecycle limit but if you created another web service for uploading of the actual email template then all you'd need to send when scheduling the emails is a bunch of addresses. It's best to repeatedly poll your web service call with small amounts of data and this is perfectly acceptable behaviour as far as google are concerned.
They'll allow you to send 2000 emails a day @ 8 mails per minute with a daily allowance of 60MB - before you get billed.
If you enable billing, these limits change to 7.4 million recipients per day with a 29 GB maximum limit on total body size and 100GB of attachments.
http://code.google.com/appengine/docs/quotas.html#Mail