One last thing. You were doing vacuum fulls but NOT reindexing, right?
I quote from the document at google docs:
13:50:00 vacuum full & analyze on all databases through pgadmin
1: Do you have evidence that regular autovacuum isn't keeping up?
2: If you have such evidence, and you have to vacuum full, vacuum full
doesn't really shrink indexes all that well.
For a heavily updated database, the 1, 2, 3 punch of autovacuum
(adjusted properly!), the background writer (adjusted properly)
smoothing things out, and the HOT updates reusing all that space
autovacuum is constantly reclaiming, meaning you should be able to
avoid routine vacuum fulls. It's made a huge difference in db
maintenance for me.
Still I do find myself in vacuum full territory once or twice a year
(rogue update or something like that on a live database). If you do
have to vacuum full then reindex. OR cluster on your favorite index.