The reason why I had this problem in the first place is that I wasn't aware that dropped columns would still count towards the columns limit in PostgreSQL. It's not a complaint, it's just ignorance. There's a difference between being ignorant and not understanding the problem after it happens. I never claimed to be an expert on PostgreSQL.
FWIW, I hope we (the PG devs) will fix that some day.
Fixed or not, PG is awesome anyway. Thanks for helping to make it the best database I've worked with so far :-)
The other part was to enable new columns to be added to that table in case we need in the future. For that part, I locked a few tables for writing, recreated them with a separate name and replaced the old with the new one in order to avoid any downtime or dealing with master-slave set-ups to be able to dump and restore without downtimes. Full vacuum freeze wouldn't reclaim that space back.