Servidor para envio de 40 mil mensagens

Galera, estou elaborando um sitezinho e o pessoal tem um lista de 40 mil e-mails mais ou menos ,pra quem eles querem enviar newsletter mensalmente.

A questão é que, eles disseram que atualmente gastam uma fortuna com uma hospedagem específica (o site já existe, vou reformulá-lo e mudar de servidor) pois somente nesta hospedagem os e-mails enviados não são classificados como spam

Vocês já ouviram falar disso?

Estava pensando em hospedar o site na Locaweb, mas com essa história não sei o que fazer.