All,
I have submitted requests to the helpdesk for wildcard support on my subdomains in DNS, and wildcard support for subdomains in apache. That's all it took to get wordpress mu working correctly.
I have a shared hosting account. It is pretty fast too.