Te sugiro a http://www.virtuaserver.com.br/ - tenho 2 VPSs (não são clouds) com 100% de uptime.

Eles tem servidores na ALOG (muito caro) e na Mundivox aqui no RJ.

Cloud no Brasil? Porque não tenta a Amazon? http://aws.amazon.com/ec2/

 

Para resolver o seu problema de DNS, poderá utilizar o próprio painel que a cPanel desenvolveu. O cPanel DNSONLY. http://cpanel.net/cpanel-whm/the-cpanel-service-distribution/dns-only/

 

Utilizando estas duas recomendações, com certeza não terá nenhum problema e irá lhe atender da melhor forma.

 

O DNSONLY irá fornecer os mesmos DNSs para seus dois servidores.