Puedes instalar en tu actual hosting algún script que gestione listas de correo y permita el envío de correos en "batch"; es decir, enviar n correos cada x tiempo. Con limitarlo a 100 por hora tu lista actual saldría en 5 horas.
Dos sugerencias:
PHPList (PHP):
http://www.phplist.com/
Dada Mail (CGI):
http://mojo.skazat.com/
Sobre conectarte con la función mail de PHP a otro servidor externo, también es posible.