Is it possible to make efficient queries that use the complete regular expression feature set.
If not Microsoft really should consider that feature.
For SQL Server 2000 (and any other 32 bit edition of SQL Server), there is xp_pcre, which introduces Perl compatible regular expressions as a set of extended stored procedures. I've used it, it works.
The more recent versions give you direct access to the .NET integrated regular expressions (this link seems to be dead, here is another one: MSDN: How to: Work with CLR Database Objects).