Have you tried setting autovacuum to run quite aggressively, perhaps juston this table? Have you tried an index on the status column only, ratherthan partial?