Problems with VACUUM and "dead row versions cannot be removed yet"

I've got an admin_sessions table on a postgres 8.0.8 server that gets
updated frequently, with about 30 live rows at any given time. We
VACUUM the table nightly, which has served us with no problems for quite
some time. Well, this morning we noticed some seriously slow queries
against the table, and VACUUM VERBOSE reported around 84,000 rows that
were "nonremovable". Same results with VACUUM FULL ANALYZE VERBOSE.

For an immediate solution, I dropped and recreated the table. However,
VACUUM still seems unable to clean up deleted rows.

Here's the output for VACUUM FULL VERBOSE ANALYZE admin_sessions, a
little while after recreating the table:

INFO: vacuuming "public.admin_sessions"
INFO: "admin_sessions": found 0 removable, 1068 nonremovable row
versions in 17 pages
DETAIL: 1031 dead row versions cannot be removed yet.
Nonremovable row versions range from 104 to 120 bytes long.
There were 0 unused item pointers.
Total free space (including removable row versions) is 6508 bytes.
0 pages are or will become empty, including 0 at the end of the table.
16 pages containing 6504 free bytes are potential move destinations.
CPU 0.00s/0.00u sec elapsed 0.12 sec.
INFO: index "admin_sessions_pkey" now contains 1068 row versions in 6 pages
DETAIL: 0 index pages have been deleted, 0 are currently reusable.
CPU 0.00s/0.00u sec elapsed 0.00 sec.
INFO: "admin_sessions": moved 0 row versions, truncated 17 to 17 pages
DETAIL: CPU 0.00s/0.00u sec elapsed 0.10 sec.
INFO: vacuuming "pg_toast.pg_toast_1215295905"
INFO: "pg_toast_1215295905": found 0 removable, 0 nonremovable row
versions in 0 pages
DETAIL: 0 dead row versions cannot be removed yet.
Nonremovable row versions range from 0 to 0 bytes long.
There were 0 unused item pointers.
Total free space (including removable row versions) is 0 bytes.
0 pages are or will become empty, including 0 at the end of the table.
0 pages containing 0 free bytes are potential move destinations.
CPU 0.00s/0.00u sec elapsed 0.00 sec.
INFO: index "pg_toast_1215295905_index" now contains 0 row versions in
1 pages
DETAIL: 0 index pages have been deleted, 0 are currently reusable.
CPU 0.00s/0.00u sec elapsed 0.00 sec.
INFO: analyzing "public.admin_sessions"
INFO: "admin_sessions": scanned 17 of 17 pages, containing 37 live rows
and 1032 dead rows; 37 rows in sample, 37 estimated total rows

Here's the SQL to create the table (nobody gets to criticize me on
schema, it's been around longer than I have):

CREATE TABLE admin_sessions (
session_id bigint DEFAULT
nextval('admin_sessions_session_id_se'::text) NOT NULL,
name TEXT DEFAULT ''::TEXT NOT NULL,
ip TEXT DEFAULT ''::TEXT NOT NULL,
first_access timestamp without time zone DEFAULT NOW() NOT NULL,
last_access timestamp without time zone DEFAULT NOW() NOT NULL,
user_id bigint DEFAULT (0)::bigint NOT NULL,
CONSTRAINT "$1" CHECK ((user_id >= 0))
);

ALTER TABLE ONLY admin_sessions
ADD CONSTRAINT admin_sessions_pkey PRIMARY KEY (session_id);

ALTER TABLE admin_sessions CLUSTER ON admin_sessions_pkey;

Executing a "CLUSTER admin_sessions" cleans up the deleted rows, but I
fully expect at least VACUUM FULL to do so as well. It does not.

Any ideas on why this is happening?

--
Nolan Cafferky
Software Developer
IT Department
RBS Interactive
nolan(dot)cafferky(at)rbsinteractive(dot)com