I've read about this online, as I want to do a simliar thing.
The problem with the "IP" solution is it will only work for one site, on one IIS install, AND someone could register a dodgy domain name and point it to your IP and they'd get your website.
What I have come up with (and waiting on the tests to confirm) is a workaround using ISAPI_Rewrite (which I suspect some of you are using anyway and have a .htaccess file with rules).
Now, my solution is to put a .htaccess file in the root folder of the Default website, something like (might need some tweaking):
RewriteEngine on
RewriteCond %{HTTPS} (on)?
RewriteCond %{HTTP_HOST} ^(?!(?:www))([^.]+)\.([^.]+\.[^.]+)$ [NC]
RewriteRule ^([^.]+)?$ http(?%1s)://www.%3/(?1$1) [NC,P,QSA]
Now, not forgetting your * DNS A record. What will happen is a user goes to whatever.mydomain.com and it will go to the IIS server, fail to find a match Host Header wise and will instead return the default website ("Under Construction" page), except with that .htaccess file and ISAPI-Rewrite it won't display the "Under Construction" page, as it will run this rule in the .htaccess file and instead pull in the equivalent from www.mydomain.com where more than likely you will have your actual .htaccess file in the root of your www website and where now you can not only specify rules for your www.domain.com but anything.yourdomain.com
Most commonly you'll want something that does http://username.mydomain.com to pull in data from www.mydomain.com/users.php?user=username for example.
If you don't have a .htaccess file with rules, then you'll just get your www.mydomain.com website but as subdomain.mydomain.com instead.
Of course if you own the server (VPS or dedicated) you can tweak this "main" rule even more, but that was a generic one I hope shared hosting IIS companies could incorporate. Perhaps with a tagline of "Dynamic Subdomains".