RFC1912 reconhece explicitamente a existência de registros MX com curinga, mas avisa
A wildcard MX will apply only to names in the zone which aren't listed in the DNS at all.
RFC4592 é um RFC de faixa padrão que esclarece a existência de curingas de MX (veja o exemplo na seção 2.2.1 ). Tenho certeza que seu provedor de DNS está, portanto, cheio disso.
Eu posso imaginar alguns softwares de DNS tendo problemas com a situação, também, porque eles não suportam registros MX curingas, ou porque eles levam a coisa "sem outros registros" um pouco literal demais e não permitem um curinga MX e um caractere curinga A. Este software não é compatível com os padrões, mas boa sorte para resolver isso.
Considerando o quão trivial é (ou deveria ser) configurar automaticamente os registros DNS quando os clientes se inscrevem, eu ignoraria totalmente os curingas e apenas configuraria seu aplicativo DNS para cada cliente.