Hardly unusual on larger tables, especially ones where the clustered index is on ascending columns and you're always querying for the latest rows.

Add an update stats ... with full scan on a regular interval. Daily if the DB has steady changes, more often if necessary. Every 5 min is probably a little too often, unless you're doing bursts of updates. Generally I prefer not to do the shotgun approach of updating all stats that may be wrong (or all stats regardless) but to target manual updates on just the tables/indexes that are known to have a problem.

I've done your second approach before, very successfully. Add an update stats with fullscan after finishing loading the day's data. Update stats shouldn't be able to cause deadlocks, it runs in read uncommitted isolation, it takes no locks other than schema stability and only a schema modification can block it.