Servidor de e-mail

Galéra, boa tarde, me encontro em uma situação muito difícil meu cliente vive tendo problemas com a locaweb e até onde eu sei eles são o melhor serviço de hospedagem do Brasil, como eu poderia fazer pra ter um serviço de e-mail pra esse meu cliente, de forma 100% segura sobre envio e recebimento?