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.
