Looks like it might be possible
http://en.wikipedia.org/wiki/SQL_Server_Full_Text_Search#Prefix_Term_Searches
Actually, it's not possible, since that's only a "begins with" search which does not work well with our tag data. On top of that, asterisks aren't possible in URLs (this was fixed in ASP.Net 4.0).
However, I implemented an experimental "explode" operator which allows you to effectively do the same thing -- it "explodes" the tags using ~ wildcards in a begins-with and/or ends-with manner.
For example:
all questions tagged bug, but without a tag beginning with "status-"
https://meta.stackexchange.com/questions/tagged/bug%20-status-~
all questions with a tag containing "edit"
https://meta.stackexchange.com/questions/tagged/~edit~
I haven't fully tested all the permutations, but you must include at least 4 characters for it to be a valid match.
Also: THIS IS EXPERIMENTAL. Like I said!
Update: You can now use *
for tag wildcards as well, for example:
https://meta.stackexchange.com/questions/tagged/bug%20-status-*
https://meta.stackexchange.com/questions/tagged/edit