Looks like it might be possible
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.
all questions tagged bug, but without a tag beginning with "status-"
all questions with a tag containing "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: