Try https://domize.com/ — Power Search, which lets you specify vowels/consonants/alpha/numbers, endings, prepositions, verbs, synonyms, or load a list of domains from a URL to a text file. Plus it's lightning fast. Not exactly regex, but it's quite powerful. My favourite domain searcher.
This is really an excellent service. I need to start using it more, instead of defaulting to my ISP, or manually whois'ing all the various domain+TLDs.
Also, Nomina on the iPhone kicks royal ass. Great way to scope out branding while on the road. Checks major domains, USPTO for trademarks, Yellow Pages, Google, the dictionary (words in dictionary for branding are good right?), Library of Congress, Thomas guide, D&B, iPhone App Store, etc. I have no affiliation to the company that make this iPhone app, but I just love it.
That regexp would allow a hyphen as the first character. How about this (still assuming .com is the only permitted TLD):
[a-z0-9][a-z0-9-]*[a-z0-9].com$
on further thought, it doesn't matter than it will match underscores, because the list of domains shouldn't have any underscores in them, but you would still want to look for underscores (maybe)
The unsettling feeling I get when doing a domainname search with any of these folks is: they keep a log of domainnames that are being searched. If something is being searched upon a lot, they themselves prolly will go and buy it. And later sell it to you for a premium price!
I would rather do a whois search from Mac/Linux/Unix) commandline.