Both plans are timing out, but one in a second and one in 10 minutes.
<QueryPlan DegreeOfParallelism="0" MemoryGrant="5968" CachedPlanSize="1632" CompileTime="659453" CompileCPU="649780" CompileMemory="715616">
<QueryPlan DegreeOfParallelism="0" MemoryGrant="7296" CachedPlanSize="1720" CompileTime=" 1183" CompileCPU=" 1055" CompileMemory=" 52024">
It is possible the slow one is due to a request for automatic statistics maintenance. If this is the case you could try setting Auto Update Statistics Asynchronously.
