Tune autovacuum analyze to run every 30mins. Seriously. The query planner needs up to date statistics.
I mean, if you could freeze statistics entirely wouldn't that fix this problem?
The old statistics said to use the index.
If it's still using old statistics, why does the behavior change?