Sounds to me like you have a an operation in your sp which can affect the way the optimizer calculates the plan. This could be something like a parameter in a join clause which dramatically changes the row counts etc... Sounds like the best thing to do would be to create the procedure using the WITH RECOMPILE option. I'd imagine that the overhead of recompilation will be low compared with using the wrong plan.