Vacuuming an index takes way too long

With current development sources, I am noticing that if I delete a large
number of entries from a table, the next vacuum on the table will spend
an *unreasonable* amount of time vacuuming the indexes on the table.

Here's a sample vacuum log:

NOTICE:  --Relation marketorderhistory--
NOTICE:  Pages 1016: Changed 0, Reapped 1016, Empty 0, New 0; Tup 8983: Vac 63439, Crash 5, UnUsed 234, MinLen 92,
MaxLen120; Re-using: Free/Avail. Space 7013200/7009228; EndEmpty/Avail. Pages 0/1015. Elapsed 1/2 sec. 
NOTICE:  Ind marketorderhistory_sequenceno_i: Pages 550; Tuples 8983: Deleted 63439. Elapsed 7876/2684 sec.
NOTICE:  Ind marketorderhistory_completionti: Pages 312; Tuples 8983: Deleted 63439. Elapsed 0/51 sec.
NOTICE:  Ind marketorderhistory_ordertime_in: Pages 273; Tuples 8983: Deleted 63439. Elapsed 1/21 sec.
NOTICE:  Ind marketorderhistory_oid_index: Pages 454; Tuples 8983: Deleted 63439. Elapsed 5047/1861 sec.
NOTICE:  Rel marketorderhistory: Pages: 1016 --> 129; Tuple(s) moved: 8983. Elapsed 2/22 sec.
NOTICE:  Ind marketorderhistory_sequenceno_i: Pages 550; Tuples 8983: Deleted 8983. Elapsed 0/3 sec.
NOTICE:  Ind marketorderhistory_completionti: Pages 312; Tuples 8983: Deleted 8983. Elapsed 0/2 sec.
NOTICE:  Ind marketorderhistory_ordertime_in: Pages 273; Tuples 8983: Deleted 8983. Elapsed 0/3 sec.
NOTICE:  Ind marketorderhistory_oid_index: Pages 454; Tuples 8983: Deleted 8983. Elapsed 1/3 sec.

Three and a half hours to vacuum a table of a few thousand entries isn't
acceptable performance in my book.  You could drop and recreate these
indexes in four seconds each (measured result); so what's going on here?

In case it helps, the indices in question are defined like so:

CREATE UNIQUE INDEX MarketOrderHistory_oid_Index on MarketOrderHistory
USING btree (oid);
CREATE INDEX MarketOrderHistory_orderTime_Index ON MarketOrderHistory
USING btree (orderTime);
CREATE INDEX MarketOrderHistory_completionTime_Index ON MarketOrderHistory
USING btree (completionTime);
CREATE UNIQUE INDEX MarketOrderHistory_sequenceNo_Index ON MarketOrderHistory
USING btree (sequenceNo);

where orderTime and completionTime are datetime fields, sequenceNo is int4.

One thing that jumps out at me is that the indexes that are taking a
long time to process are unique indexes.

            regards, tom lane