Why different datetimes freezes a query based on indexes?
We have had the similar issue when dealing with big (billions of records) tables. As Martin Smith suggested in comment - you would probably need to periodically rebuild statistic data on that table.
This worked for us:

UPDATE STATISTICS &lt;TABLE NAME&gt; WITH FULLSCAN 


This solution is kind of brute-force and being too simple but still it may help.