Slow access to table in postgresql despite vacuum
1)  I would have tried cluster followed by analyze.  My only hesitation is I am not 100% sure what happened here.  Is it possible there was some index corruption as well?  Reindex might have helped? Given that the stats entries were way off, is it possible something was corrupt elsewhere regarding the relation's OID?

2)  I have no idea.  I have never seen anything like that before.  I would need a lot more diagnostic information even to hazard a guess.  If it happens again it would be worth knowing the physical size of the table, for example.

Edit:  Remembering that 8.4 still had max_fsm_pages, if that was set too low between vacuums that could cause this sort of table bloat.

Edit2:  Vacuum full, however should have been able to handle bloat due to max_fsm_pages, at least it does in my experience, suggesting again to me that something deeper was wrong.