I am guessing that VACUUM only kicks in for row deletions? With that busy a table, can't you just bypass VACUUM and reuse dead keys? I am assuming because you are talking indexes here, you are talking fixed length records and not dynamically allocated VARCHARs etc.??
Postgres uses MVCC, which is basically copy-on-write: every UPDATE to a row actually creates a new row. Once all transactions that could see the old row have finished, the old row can be pruned.
