Eric Blinn walks us through what might cause a query plan not to be used:
There are several reasons that a query plan would need to be compiled again, but they can be boiled down to a few popular reasons.
The first one is simple. The plan cache is stored exclusively in memory. If there is memory pressure on the instance SQL Server will eject plans from cache that aren’t being used to make room for newer, more popular plans or even to expand the buffer pool. If a command associated to a plan that has been ejected from the plan cache is issued, it will need to be compiled again before it can execute.
Since SQL Server 2008 a system stored procedure, sp_recompile, has been available to clear a single stored procedure plan from the cache. When executed with a valid stored procedure name as the only parameter any plans for that procedure will be marked for recompilation so that a future execution of that procedure will need to be compiled. Running sp_recompile does not actually compile the procedure. It simply invalidates any existing plans so that some future execution, which in theory may never come, will need to compile before executing.
Read on for additional causes.