and I bet if you run the alter script (as above) the app suddenly reports quick run times?
I totally agree with Kev Riley. Such search procedure cannot have a good plan for every scenario. It could run good for few scenarios and would be awful for some others, depending upon the data.
Have you tried OPTION(RECOMPILE) hint?