I hit this issue all the time and it is never easy or fast to fix once postgres stops accepting writes. If you have a write heavy postgres database, the autovacuum settings are not sufficient. The entire database needs to be vacuumed aggressively.
Then you tune it to run more aggressively. There are configuration parameters specifically for this.
Curious to know your problem space and context? User generated content? Sensor logs?