Xapian supports a query syntax which uses a trailing '*', but it's not a true wildcard/regexp, it's a range search on an ordered index. Notmuch allows you to use that syntax, see http://notmuchmail.org/searching/

It can do simple wildcarding with the * character, but I'm not aware of any general regexp capability, same as with any indexed database. Since you still have the underlying maildirs you can always just use egrep I guess.