A manual "Vacuum full analyze" fixes it immediately.
But... .shouldn't autovacuum prevent this? Is there some way to look in a
log somewhere and see if and when the autovacuum is being run - and on
what?
Are your FSM settings enough to keep track of the dead space you have?