Supondo que você conheça os subdomínios que seus clientes estão usando, você deve configurar as entradas de DNS para cada um deles, apontando para o controlador de domínio que cada um deve usar. Muitos provedores de DNS hoje em dia têm "APIs" baseadas em HTTP ou qualidade variável que você pode usar para atualizar automaticamente registros DNS quando seu banco de dados de aprovisionamento é atualizado (> delete DNS > delete DNS registro). Se você estiver hospedando o DNS por conta própria, poderá facilmente criar um script para gerar os dados da zona DNS a partir dos registros de seus clientes.
Os curingas de DNS são malignos, confusos e não fazem o que você provavelmente acha que eles fazem. Eu recomendo strongmente que você pare de usá-los e nunca deixe que eles escureçam sua porta novamente.