If you're getting lots of inserts there's a good chance that during the day a healthy chunk of the information added to the table are falling outside of the statistics. When the data can't be found in the stats, the optimizer will make radically different choices. So, possibly, you can update stats more often during the day (maybe sampled instead of FULL SCAN to avoid contention, and yeah, there is some). Also, I'd suggest looking into traceflag 2371 to change when the automatic update of statistics occurs. By default, you have to modify 20% of the table to see a change. If you have a large table, this may take a while. The traceflag changes that behavior. Another option, not my favorite, is to look at KEEPFIXED PLAN hints. I find these to be a little dangerous, but it is an option. I'd make it the last possible option though.