Sugestão de servidor

Olá pessoal. Na paz?

Tenho um cliente que tem um projeto hospedado na UOLHost, porém a UOL está com sérios problemas no envio de e-mails para servidores como GMail e Yahoo e com isso ele está tendo sérios problemas com os clientes dele.... Alguém poderia me indicar um bom servidor, mas que seja empresa mesmo. Tentamos um orçamento na Amazon e no Google, mas como ele está começando agora, os valores ficaram acima do  esperado.

Obrigado