So what is the problem? The problem is they weren't running Autovacuum. Now many of my brethren would say, "HERESY!" but in reality there are good reasons not to run Autovacuum (although I would say not Autoanalyze). Autovacuum is unpredictable, and can cause performance problems. 99% of the time you should run Autovacuum but there is a 1% reason to consider other alternatives.
The point I trying to make here in my sleep deprived state is that Autovacuum can be turned on with just a reload. It does not require a restart. I swore up and down that it required a restart and I ended up being wrong. I am not sure why I thought it needed a restart.
So there you go folks. Tip of the day, "autovacuum = on" only needs a reload.
Tallyho read the docs!