What is a good guideline for sampling for statistics updates
If you always query the tail, you can give a shot to filtered indexes. Index 10 ways with, say,  WHERE datetimecolumn &gt; @INDEXBUILDDAY-30. Periodically (daily, weekly?) you can move this filter forward by adding (online) a new set of filterd indexes and then dropping the old ones. With a much smaller size and a much more recent build (implying recent stats), they would be 'fresh' and very appetizing for the optimizer. The periodic rebuild doesn't even need to scan the base table (no huge IO, no BP cache pollution), the old filtered index should always be usable as a source to build the next filtered index (it covers it).

For those queries that land outside the covered filtered tail, you can keep some (less than the 10 ways hopefully) full, unfiltered indexes. With the right voodoo invocation the optimizer might get your point and use the filtered ones when appropriate and only resort to the full ones when necessary...