VACUUM slow on small table

Environment: Postgres 7.2.3 under Linux (RH 7.3, 2.4 kernel)

We have a table used as a job queue by several background applications.
This table gets around 25K inserts and deletes per day, with something
like another 25K updates of each of several columns. All this activity
causes the indexes to be nearly useless, unless the table is VACUUMed
very frequently.  At present, this amounts to around every 5-10 minutes
(it's actually based on activity in the table, but it works out to around
that).

The table undergoes VACUUM FULL every night. However, it still shows
hundreds of thousands of tuples after such vacuuming.

Today, the normal VACUUM took upwards of 15 minutes to perform, instead
of the usual handful of seconds. I finally threw up my hands, dumped the
table with pg_dump, dropped it, and re-created it.

What's going on? Doesn't VACUUM under 7.2.3 do a thorough job of clearing
up deleted rows?  Should I REINDEX this table nightly as well?  Does
drop and recreate clear things up even better?

--
Jeff Boes                                      vox 269.226.9550 ext 24
Database Engineer                                     fax 269.349.9076
Nexcerpt, Inc.                                 http://www.nexcerpt.com
           ...Nexcerpt... Extend your Expertise