Slow access to table in postgresql despite vacuum

Question

I'm running PG 8.4

I had a table with about 20K records. Any query accessing this table with more than 1 record (e.g. joins) would be very very slow. Even a count would take like 20 seconds.

Stats showed 5 million live_tuples.

I tried vacuum, vacuum analyze, and in the end, vacuum full. Nothing changes in terms of speed. And stats still showed the same thing.

I ended up creating a new table, insert all records in the new table and drop/rename the old one.

The new table now runs lightning fast.

Any idea of:

1) What would have been the more correct handling? I'm looking for a better way to do this as one of the side effect is that the views which were pointing to the table got modified by the "alter table rename to" statement and unbeknownst to me, the views were pointing to the old table for 2 days!

2) Why would that happen in the first place?