Primeiro, um editorial: forçar você a usar seus servidores DNS me faz cara feia.
Isso está fora do caminho ...
Você está praticamente preso usando o deles. Tudo se resume a resolver 'example.com'. Um registro como esse tem que ser um registro A, não um CNAME. Existem boas razões para isso . Se eles puderem saber qual é o endereço IP da máquina específica, eles precisam hospedar o registro A. E isso significa hospedar a zona DNS.
O mesmo mecanismo funciona no Amazon AWS. Um Elastic Load Balancer pode ter qualquer endereço IP. No entanto, quando você define o registro em seu serviço DNS (Route53), você o faz como um registro A referente ao ELB. Eles podem fazer isso porque eles escreveram seus servidores DNS e podem servir o endereço IP correto toda vez que forem solicitados. É o recurso 'pode mudar sem aviso prévio' que força isso, caso contrário você poderia hospedar o registro A em sua própria zona DNZ.
O 'www' pode ser um CNAME sem problemas.