[edit] The right model might be a sort of meta-search engine - feed the regex to something like Wikipedia to determine plausible keywords and then return aggregated search results based on the keywords. At prototype and small scale actual search results could be aggregatte from other search engines such as Google or Bing.
[edit] Interestingly, Wikipedia already has regex capability built in to AutoWikibrowser.
http://en.wikipedia.org/wiki/Wikipedia:AutoWikiBrowser/Regul...