Should one always VACUUM ANALYZE before REINDEXing in PostgreSQL 8.4?

If the CREATE INDEX statement sees that another session holds an active snapshot that might still be interested in the deleted records, then it includes those deleted records into the new index.

Similarly, if a REINDEX sees that another session holds an active snapshot that might still be interested in the deleted records, then it includes those deleted records into the new index.

If a VACUUM sees that another session holds an active snapshot that might still be interested in the deleted records, then it keeps those records in the table. And then the REINDEX or CREATE INDEX also need to carry them into the new index, as long a the snapshot still exists.

Once there or no longer any snapshots that could possible see the deleted rows, then the VACUUM may remove them from the table. But a CREATE INDEX or REINDEX could also just not carry them over into the new index, whether VACUUM had gotten around to removing them from the able or not.

So in your scenario, the role of the VACUUM between the initial CREATE INDEX and REINDEX is probably just to take up time, during which time your long-running transaction hopefully goes away on its own and drops the interfering snapshot.