autovacuum not freeing up unused space on 8.3.0

It appears (and I am open to correction) that autovacuum is not
operating correctly in 8.3.0. I have a vanilla installation where
autovacuum is enabled, and is running with all the default settings.

I have a table which is continually having rows added to it (~50/sec).
For the sake of this example I am limiting it to 20000 rows, which means
that I am continually having to remove rows (100 at a time) as I get to
20000.

When I get to 20000 rows for the first time the table disk size (using
pg_total_relation_size) is around 5MB. Since the autovacuum only kicks
in after a while I would expect it to get a little bigger (maybe 6-7MB)
and then level out as I am cycling through recovered rows.

However the table disk size continues increasing basically linearly and
when I stopped it it was approaching 40MB and heading up. During that
time I was running ANALYZE VERBOSE periodically and I could see the dead
rows increase and then drop down as the autovacuum kicked in - the
autovacuum worker process was running. It didn't seem to free any space
though. In fact a VACUUM FULL at this point didn't help a whole lot either.

I ran the same test but using manual VACUUMs every 60 seconds and the
table size leveled out at 6.6MB so it appears like a normal vacuum is
working. I changed the normal VACUUM to have the same delay parameters
(20ms) as the autovacuum and it still worked.

So it appears to me like the autovacuum is not freeing up dead rows
correctly.

I turned on logging for autovacuum and ran the same test and saw the
following messages:

LOG: automatic vacuum of table "metadb.test.transactions": index scans: 1
pages: 0 removed, 254 remain
tuples: 4082 removed, 19957 remain
system usage: CPU 0.02s/0.02u sec elapsed 1.11 sec
LOG: automatic vacuum of table "metadb.test.transactions": index scans: 1
pages: 0 removed, 271 remain
tuples: 5045 removed, 19954 remain
system usage: CPU 0.03s/0.03u sec elapsed 1.54 sec
ERROR: canceling autovacuum task
CONTEXT: automatic vacuum of table "metadb.test.transactions"

At this point I had deleted 32800 rows as can be seen from the query
below, although the logs only indicated that around 10000 rows had been
freed up.

select min(transaction_key),max(transaction_key) from test.transactions;
min | max
-------+-------
32801 | 52750

Is there anything I have missed as far as setting this up is concerned,
anything I could try? I would really rather use autovacuum than manage
the vacuums of a whole lot of tables by hand...

Thanks
Stuart

PS. Running on NetBSD 3