I would suggest figuring out a way to send those e-mails in smaller packages out - the shared hosting servers have a limit of 300-400 e-mails per hour and 20 per minute. Both PHPList and DadaMail have ways to spread the sending out over a long period of time, so you don't reach the hard limits of the server.
As for the cause, you can thank spammers from around the world. They have really lead to every web host out there having to limit the number of e-mails that can be sent like this.

Hope that helps some.
