ANALYZE getting dead tuple count hopelessly wrong

I have a table with about 15 million rows which is constantly having
tuples added to the head and deleted in blocks from the tail to maintain
the size. The dead tuple count in pg_stat_user_tables tracks the deleted
rows fairly accurately until an auto-ANALYZE is done in the background
at which point the value it calculates is wrong by a factor of 2-3 times
(calculated value is 30-50% of the correct value), which completely
throws the auto-VACUUMing. An example is that the auto-VACUUM only ran
when there were 12 million (real) dead rows! Any ideas?

Thanks
 Stuart

PS. Running 8.3.1 on NetBSD 3.