The following search:
http://stackoverflow.com/questions/tagged/c%23~ returns "43,619 questions tagged c#"
Note the single tag in the results despite the wildcard in the search term. However, the following search:
http://stackoverflow.com/questions/tagged/.net~ returns "26,058 questions tagged .net or .net-3.5 or .net-2.0 or .net-1.1 or .net-4.0 or [lots of other terms beginning with .net]"
This is what I would expect.
The same is true if you search for "c++*" (or more accurately "c++~").
I'm guessing it has something to do with the way # is encoded as %23 and + as %2b.
Apparently it's by design - though I'll leave the question open for now in case the 4 character limit can be lifted.