>One action we have consiously not done is "REINDEX" on the
>table. We want to avoid that as far as possible.
Why? It's usually a very painless step, unless the table has millions and
millions of rows. We reindex tables with multiple indexes and several million
rows on a weekly basis. The only downside is that the table seems to be quite
"busy" during the process, which only takes a few minutes.
AFAIK, VACUUM doesn't reclaim space taken up by indexes. In fact, the more
deletes you do, the larger the index space gets, and the *slower* the index
performs. A periodic REINDEX cleans up a lot of problems.