Well the answer is easy, use a custom authentication provider. The out of the box the AD provider is not up to the task as it means that all users can see all others. Next thought would be to use the forms based one, but that means additional replication of users from AD to a database which is also a pain. MOSS also includes a generic LDAP provider which seems like the perfect fit as you can specify the root OU to start from (so limiting what each site can see), but this provider is very error prone due to the HMC structure/properties so in the end you are better off building your own LDAP one. So all you need to do once the custom authentication provider is build a custom provider for HMC which setups and manages the site creation and feeds the information on what a customer has directly to HMC.
A great example of how this is done, is one of our first customers who got their own mini-environment within our hosted environment. So they don't sit on our big MOSS farm, they have their own one and have some special customizations to it, but the principals of their solution and the HMC one is very similar. The customer is South African Tourism's (SAT) and their web site is www.freesatsite.co.za. One of the special changes is the use of specialised custom authentication provider, which was changed from an LDAP one to one that uses Windows Live! So your MSN login becomes your web site login (how cool is that) and it includes a full self provisioning system which allows SAT members to login, and provision a new site in seconds. Rather than being completely separate domains each new web site is a sub-site of www.freesatsite.co.za. Please don't think I suddenly became a great MOSS expert, I really just provided servers and the environment for this brilliant solution, the team that built this solution are the guys from Blacklight who designed the UI and all the themes support and to Mark Lenferna de la Motte and his team who did the bulk of the heavy lifting configuration to make MOSS do it's magic.