I'm not sure you can avoid it for that query, but you can inject intelligence into your application. If you have exact searches, then use a query (or proc) that works for those. If you need less exact searches, then switch to a new proc and take the hit.

Code is fairly cheap and you don't necessarily have to reuse stuff if there's a performance hit.

You have to compare the cost and time of developing (and maintaining) more procs v the hit your users and systems take. If you have any sort of search volume, it's worth doing a little work to optimize different searches.