Understanding statistics, execution plans, and 'ascending key problem'
Am I correct in saying that statistics are only used when creating the execution plan


No, out-of-date statistics may cause an optimality-related recompilation of the affected statement.


  We have an ascending date/time column in one of our largest tables that we query regularly


Sub-optimal execution plans caused by predicate values being outside (specifically above) the range of values stored in the corresponding statistics histogram is known as the Ascending Key Problem. Rebuilding statistics is one possible solution, but it can be quite resource-intensive. Alternatives include:


Trace flags 2389 and 2390. This requires that an index exists with the problematic column as the leading key. It does not work with partitioned tables, and is only effective in SQL Server 2014 if the original cardinality estimator is used. Trace flag 4139 may also be required if the statistics object is branded stationary.
Upgrade to SQL Server 2014. The new cardinality estimator includes logic to estimate beyond the histogram using average density information. This can be less accurate than the 2389/2390 trace flags in some important circumstances.
Enable more frequent automatic statistics updates for large tables with trace flag 2371. With this trace flag, instead of updating after 20% + 500 changes, only SQRT(1000 * Table rows) modifications are required. This is not as complete a solution as those mentioned previously, as updates may still not be triggered often enough.


If the source of your problem is not so much frequent plan compilations based on beyond-histogram predicate values, but more about the effects of occasionally caching such a bad plan as a result of parameter sniffing, you could also consider:


Disabling parameter sniffing using trace flag 4136
Using OPTIMIZE FOR (@parameter = value) to compile a plan for a known representative value
Using OPTIMIZE FOR (@parameter UNKNOWN) to optimize using the average distribution
Using OPTIMIZE FOR UNKNOWN (same as 4136, but per-query)
Using OPTION (RECOMPILE) to compile every time, sniffing the particular value. If the vast majority of runtime values are within the histogram, this may be effective.


For more information about parameter sniffing, embedding and the recompile options, see my article on SQLperformance.com.