De acordo com a RFC 1123, o registro MX não pode apontar para um CNAME. Se eu estivesse na sua situação, eu configuraria mail.ourdomain.com como um registro A apontando para o novo endereço IP do fornecedor e depois rapidamente mudaria todos os registros MX para os dados corretos. Em seguida, informe por que a alteração dos registros MX é tão difícil em sua organização.
Dito isso, a maioria dos servidores de e-mail ainda envia e-mails para um CNAME; no entanto, você não pode garantir isso.