Statistics mismatch between n_live_tup and actual row count

Hi,

we're currently investigating a statistics issue on postgres. We have some tables which frequently show up with strange values for n_live_tup. If you compare those values with a count on that particular table, there is a mismatch of factor 10-30. This causes the planner to come up with very bad plans (we also have this issue on bigger table like the one below).

db=# SELECT relname, n_live_tup, last_analyze, last_autoanalyze FROM pg_stat_user_tables WHERE schemaname = 's' AND relname = 't';
relname | n_live_tup | last_analyze | last_autoanalyze
----------+------------+-------------------------------+-------------------------------
t | 7252 | 2011-12-08 03:00:02.556088+01 | 2011-12-01 18:29:00.536321+01

db=# SELECT COUNT(*) FROM s.t;
count
-------
280

The strange thing is, if we run an ANALYZE on this table, the statistic is good. 10 minutes later it's bad again. We suspect one of our processes which might do unnecessary (i.e. blind) updates. Can this be the cause of the statistics problem?

PostgreSQL 9.1.1 on x86_64-unknown-linux-gnu, compiled by gcc-4.6.real (Debian 4.6.2-4) 4.6.2, 64-bit

The migration to 9.1 did not fix this problem, as we already have this since 8.4.

I can provide all postgres configuration, but I don't see anything we changed (compared to the default config), which might be related here.

Any clue appreciated here!

Best regards
Andy