Why are my statistics getting out of date so quickly?
Time spent automatically updating statistics is included in compile time.  The stats update takes 10 minutes, and the compile time for a query that triggers an auto stats update includes that time - which is why the query takes over 10 minutes every now and then.

The modification threshold for an automatic stats update, per the documentation, is

sqrt(table cardinality * 1000)


With your numbers (300,000,000 rows), you hit that threshold at 547,722 modifications.

Since 1,000,000 rows are being added every day, you're bound to hit an auto stats update around twice a day.

Since your query's estimates are good before and after the stats update, one possible solution would be to enable the database level AUTO_UPDATE_STATISTICS_ASYNC setting.  This still let's SQL Server update stats automatically, but it's done asynchronously (so queries don't have to wait on it to happen):

ALTER DATABASE [Live] 
SET AUTO_UPDATE_STATISTICS_ASYNC ON;


Note that this affects the entire database, not just that table / statistic.