Vacuum (even FULL) isn't the most efficient when it comes to reclaiming space from bloated indexes. And in PostgreSQL 8.x it was even more the issue.
I do remember reading about tests where dump, drop and restore might be indeed faster and gets better results than vacuum full.
And this is what I would suggest if possible.
There is another option you might try first though, quoting PostgreSQL 8.4 documentation:
The FULL option is not recommended for routine use, but might be useful in special cases. An example is when you have deleted or updated most of the rows in a table and would like the table to physically shrink to occupy less disk space and allow faster table scans. VACUUM FULL will usually shrink the table more than a plain VACUUM would. The FULL option does not shrink indexes; a periodic REINDEX is still recommended. In fact, it is often faster to drop all indexes, VACUUM FULL, and recreate the indexes.