I would suspect that vacuuming these tables would solve your problem. Whether there is an issue beyond a lack of vacuuming, or related to auto-vacuum, I am unsure. Though at this point it may take a vacuum full to recover back to a sane state. Though ANALYZE by itself should clear up the statistical discrepancy.
A nightly VACUUM FULL which ran based on heuristics resolved the problem. This would seem to point to a db problem more than an app problem? I’m unsure how the app could have an affect of this magnitude on the database, although I’d love to be told otherwise.
