I have followed the excellent instructions on how to provide access to websites prior nameservers are propagated given on: http://www.virtualmin.com/documentation/id,frequently_asked_questions/#h...
Another way, which I believe is the best option (saving the best for last!) and most closely matches what you're currently used to without the security implications, is the Automatically create alias domain option (found in every Server Template, though to keep it simple you can just edit the Default template). Just select the radio button beside "Create under" and fill in the domain under which you'd like all of your customer domains to appear.
This option will cause Virtualmin to create a subdomain under your domain for every new domain you create--this will be immediately accessible with a name like "newdomain.mydomain.tld". Easy to remember for the user (because it's their domain name, plus the name of the company they're hosting with), and it isn't a path-based automatic thing, so non-virtual host home directories won't be potentially exposed in any way, as with the Automatic virtual hosts method above (as used by Ensim, cPanel, and others, I reckon). If you need public access to sites, this is the method you really want. Note that this method also does not break SuExec, as the automatic hosts option does, so CGI scripts (and PHP once we get FastCGI+SuExec working) will run as the user that owns the domain...this is safer.
Now I can create virtual servers, which can be accessed via 'subdomain.maindomain.tld' untill their domains are propagated. Now my concern is won't search engines double scan this kind of sites on 'subdomain.maindomain.tld' and 'subdomain.tld' (after they are propagated and become accessible)? Won't they punish 'maindomain.tld' and 'subdomain.tld' in terms of SEO points for this kind of setup?