Primeiro, os registros MX não são registros SRV.
Segundo, ele está absolutamente certo. Eu lido com esse problema com frequência com um dos meus clientes que também hospeda o Exchange para seus clientes. O Outlook precisa encontrar informações de descoberta automática que aponte para o servidor do Exchange. O problema em ter um registro curinga é que ele causa autodiscover.domain.com
para resolver seu servidor da Web, o que impede que o Outlook localize o arquivo XML de descoberta automática e conecte-se ao Exchange, motivo pelo qual seu host de email está solicitando a remoção do registro curinga.
A solução alternativa seria hospedar o arquivo XML de descoberta automática em seu servidor da Web (consulta de domínio raiz HTTPS) conforme relacionado nos artigos vinculados. Como você pode ver nos artigos, há uma ordem definida de operações que o Outlook usa para localizar as informações de descoberta automática. Você pode ver nos artigos que o terceiro método de descoberta é aquele com o qual seu curinga está causando problemas (consulta de domínio de Descoberta Automática HTTPS).
O quinto método é o que o seu hoster do Exchange está usando para seus clientes.