The warning, while perhaps technically accurate, makes me think something is seriously wrong and raises my blood pressure.

I think of it like this: if you type in a bad regex, you did something wrong and deserve a warning symbol. If you just type a short string, it's our fault--a technical limitation--that you can't get an accelerated search out of that. This bubble should be more like an apology than an accusation.
Remove dead removeUserMessage().
Make the no-results message more visually subtle. Fix bug 965650.

Also change the class name: the only use of this template left is saying "no results". A future bug will factor out all the repetition and improve the message itself.