A long time ago, I had blogged about the perils of ‘wildcard’ query patterns. As a response to one of the comments in that post, I learnt about a new optimization introduced in SQL 2008 wherein the OPTION (RECOMPILE) hint would help in these kind of cases. Ever since then, I had used this in some customers; but recently, I found that on SQL 2008 R2 and even in SQL 2008 SP1, the behavior was not working correctly.
Recently, I found the reason for this issue from some other sites, and I also found the official name for this enhancement: Parameter Embedding Optimization. It turns out that, based on some bug reports, this optimization was disabled starting in SQL 2008 CU4 (and also disabled in SQL 2008 R2 RTM). The fixes for the issue are in SQL 2008 SP1 CU5 and SQL 2008 R2 CU5 respectively.
Here are the links which cover the details, and I hope they help you!