Não está completamente claro o que o seu plano geral implica, mas aqui estão alguns esclarecimentos sobre como os registros de curingas funcionam em geral. Eu acho que isso deve esclarecer o que pode ser um problema.
Os registros curinga não cobrem o nome base (ou seja, *.example.com. não cobre example.com. ).
Os registros curinga nunca se sobrepõem a nada, seja CNAME ou qualquer outro tipo de registro.
Wildcard RRs do not apply:
...
- When the query name or a name between the wildcard domain and the query name is know to exist. For example, if a wildcard RR has an owner name of "*.X", and the zone also contains RRs attached to B.X, the wildcards would apply to queries for name Z.X (presuming there is no explicit information for Z.X), but not to B.X, A.B.X, or X.
(ênfase adicionada)
Diferente do acima, que pode ou não ser um problema para o que você tinha em mente, você tem certeza de que realmente quer nomes aleatórios que as pessoas na Internet inventarem para ter MX registros (por exemplo, <obscenityofchoice>.example.com e o que quer que seja)?