O problema é que você não pode ter um registro CNAME para um domínio que tenha outros tipos de registro. É por esse motivo que você nunca deve ter um registro CNAME para seu domínio raiz (mydomain.com).
Parece que você tem as respostas certas:
- Mantenha o registro MX para mydomain.com direcionado para o Google.
- CNAME alias seu registro www para mydomain.cloudapp.net.
- Crie um redirecionamento de mydomain.com para www.mydomain.com (via
.htaccess
rewrite-rule ou uma página básica de redirecionamento de HTML hospedada em mydomain.com).