Hi,
I've done my Googling, and it looks like this is a fairly common problem. In my case, there's a collection of hundreds of databases (10 GB+) with apps which are pretty much designed (a long time ago) with heavy use of temp tables - so a non-trivial system.
The databases are vacuumed (not-full) daily, from cron (autovacuum was turned off some time ago for performance reasons), and still their size increases unexpectedly. By using some of the queries floating around on the wiki and stackoverflow[*], I've discovered that the bloat is not, as was assumed, in the user tables, but in the system tables, mostly in pg_attributes and pg_class.
This is becoming a serious problem, as I've seen instances of these tables grow to 6 GB+ (on a 15 GB total database), while still effectively containing on the order of 10.000 records or so. This is quite abnormal.
For blocking reasons, we'd like to avoid vacuum fulls on these tables (as it seems like touching them will lock up everything else).
So, question #1: WTF? How could this happen, on a regularly vacuumed system? Shouldn't the space be reused, at least after a VACUUM? The issue here is not the absolute existence of the bloat space, it's that it's constantly growing for system tables.
Question #2: What can be done about it?
This is PostgreSQL 9.3, migrating soon to 9.4.