Note that with pgsql, the older the version you're running, the
greater your pgsql-fu must be to keep it happy.
With autovacuum and more efficient vacuuming all around in later
versions, your simple first step is to upgrade to 8.4.1 or 8.3.8 as
soon as possible. Until then, dump / reload that table and / or
vacuum full and reindex it and / or cluster that table (did we have
cluster in 7.3? Been too long, can't remember).
In simple terms, please stop torturing yourself with an old and pretty
much unsupported pg version.