Catalog bloat (again)

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.

[*] https://wiki.postgresql.org/wiki/Show_database_bloat ,
http://stackoverflow.com/questions/13931989/postgresql-automating-vacuum-full-for-bloated-tables