Ojo porque quizas este Sr. de nick raro lo que quiere es crear subdominios para sus usuarios, o dar algun servicio y lo que conviene
NO es editar las zonas de DNS.
Cuando un cliente me presento un problema similar, la solucion que le di fue muy simple. Instale DJB Dns en el *nix que tenia, cree unas reglas simples y defini
www.dominio.com smtp.domini.com webmail.dominio.com y que *.dominio.com tambien apuntara a la ip del server web.
-Esto tambien requeria la directiva server alias en el virtual host de apache -
Desde la aplicacion web chequeaba el desde que HTTP_HOST se habia entrado y listo.
Si no puedes editar la configuracion de apache, podrias tambien crear un .htaccess y manejar el tema con Error_document 404..