I've got a table that grows under Postgres 9.1. It's a high-throughput table with lots of inserts and deletes, but it should generally remain between 1-2k in terms of number or records. Auto-vacuum is enabled, and we've run manual vacuums. We've checked for locks and there don't appear be any. Running "vacuum verbose;" says that while there are millions of dead records, but "found 0 removable".
What might I have not thought about?