Sending out mass emails

For the first time in a few years I sent out a mass email newsletter to all my members. all 250K+ of them. After about 40k had been sent, I started get the emails blocked by yahoo and hotmail etc. I talked to my host and they said sending any mass emails like that will always be seen as spam and that i need to use a service that specializes in that instead of sending from my host server.

How do you guys handle sending out tens and hundreds of thousands of emails?

edit: I think I need a bulk SMTP service. anyone recommend one?

At work we use MailChimp which works pretty well (although it may get a bit expensive for 250K+ mails, plus I’m not sure if they offer an SMTP only service). You could also check out http://www.smtp.com or http://www.email-unlimited.com/bulk-email-smtp-server.html
I don’t know anything about the quality of those last two though, so I can’t vouch for them.