Parameter Sniffing vs VARIABLES vs Recompile vs OPTIMIZE FOR UNKNOWN

So we had a long running proc causing problems this morning (30 sec + run time). We decided to check to see if parameter sniffing was to blame. So, we rewrote the proc and set the incoming parameters to variables so as to defeat parameter sniffing. A tried/true approach. Bam, query time improved (less than 1 sec). When looking at the query plan the improvements were found in an index the original wasn't using. Just to verify that we didn't get a false positive we did a dbcc freeproccache on the original proc and reran to see if the improved results would be the same. But, to our surprise the original proc still ran slow. We tried again with a WITH RECOMPILE, still slow (we tried a recompile on the call to the proc and inside the proc it'self). We even restarted the server (dev box obviously). So, my question is this... how can parameter sniffing be to blame when we get the same slow query on an empty plan cache... there shouldn't be any parameters to snif??? Are we instead being affected by table stats not related to the plan cache. And if so, why would setting the incoming parameters to variables help?? In further testing we also found that inserting the OPTION (OPTIMIZE FOR UNKNOWN) on the internals of the proc **DID** get the expected improved plan. So, some of you folks smarter than I, can you give some clues as to whats going on behind the scenes to produce this type of result? *On another note, the slow plan also get's aborted early with reason GoodEnoughPlanFound while the fast plan has no early abort reason in the actual plan.* In summary - Creating variables out of incoming parameters (1 sec) - with recompile (30+ sec) - dbcc freeproccache (30+ sec) - OPTION (OPTIMIZE FOR UKNOWN) (1 sec) **UPDATE:** See slow execution plan here: https://www.dropbox.com/s/cmx2lrsea8q8mr6/plan_slow.xml See fast execution plan here: https://www.dropbox.com/s/b28x6a01w7dxsed/plan_fast.xml *Note: table, schema, object names changed for security reasons.*