Bloated tables and why is vacuum full the only option

Hello list.

I know all the theory about vacuuming. I've got log tables that get
periodically pruned. The pruning is... quirky, though. It's not so
much deleting data, as summarizing many (thousands) of rows into one
single row. For that, a combination of deletes and updates are used.

In essence, the tables are write-only except for the summarization
step for old data.

Many tables are becoming increasingly bloated, which is somewhat
expected due to this usage pattern: I had expected table size to be
about constant, holding recent data plus archived old data (which is
really small compared to full recent logs), with some constant-sized
bloat due to daily summarization updates/deletes.

What I'm seeing, though, is not that, but bloat proportional to table
size (always stuck at about 65% bloat). What's weird, is that vacuum
full does the trick of reducing table size and bloat back to 0%. I
haven't had time yet to verify whether it goes back to 65% after
vacuum full (that will take time, maybe a month).

Question is... why isn't all that free space being used? The table
grows in size even though there's plenty (65%) of free space.

I've got autovacuum severely crippled and that could be a reason, but
I do perform regular vacuum runs weekly that always run to completion.
I also do routine reindexing to stop index bloat on its tracks, yet
freshly-reindexed indexes get considerably reduced in size with vacuum
full.

Is there some case in which regular vacuum would fail to reclaim space
but vacuum full would not?

I'm running postgresql 9.2.5. If this was 8.x, I'd suspect of the free
space map, but AFAIK there's no such limit in 9.2. Relevant
non-default settings are:

"archive_mode";"on"
"autovacuum_analyze_scale_factor";"0.05"
"autovacuum_analyze_threshold";"500"
"autovacuum_max_workers";"1"
"autovacuum_naptime";"900"
"autovacuum_vacuum_cost_delay";"80"
"autovacuum_vacuum_cost_limit";"100"
"autovacuum_vacuum_scale_factor";"0.1"
"autovacuum_vacuum_threshold";"500"
"bgwriter_lru_maxpages";"200"
"checkpoint_completion_target";"0.9"
"checkpoint_segments";"64"
"checkpoint_timeout";"1800"
"maintenance_work_mem";"1048576"
"vacuum_cost_delay";"20"
"wal_level";"archive"

[0] http://labs.omniti.com/labs/pgtreats/browser/trunk/tools/pg_bloat_report.pl