Incorrect Statistics EQ_ROWS Causing Parallel Table Scans and Deadlocks
As pointed out by sp_BlitzErik (thank you!), the problem here was the sampling rate was too low for the billion row transaction table.  The more rows sampled by the statistics update, the more accurate the estimate, but the longer it takes for SQL Server to generate the statistics.  There is a tradeoff between database maintenance time and statistics accuracy.

A simple `update statistics MyTable' was sampling 0.13% of the rows.  This generated a very poor estimate for the "EQ_ROWS" column that was usually hundreds of times worse than the actual row counts.  For example, some EQ_ROWS estimates were over 60,000 when the actual counts were about 150.  On the other hand, the default stats update completed in 25 seconds-- pretty fast for a billion rows.

A full scan generated perfect EQ_ROWS statistics.  However, the full scan required about 5 hours to complete.  That would not be acceptable for the customer's database maintenance window.

Below is the chart of samples vs. accuracy.  We're going to recommend the customer adjusts the sample size manually for the largest tables in the system.  I expect we'll go with a sample size of about 10%.  The Avg Stat Diff column is calculated as ABS(EQ_ROWS - ActualRowCount).

Sample Size     Avg Stat Diff Time to Create Stats
 =============== ============= ====================
 Default (0.13%)        42,755             00:00:25
 1%                      4,880             00:02:41
 5%                        940             00:13:47
 10%                       443             00:27:45
 20%                       209             00:56:28
 50%                        67             02:24:17
 100% (fullscan)             0             ~5 hours