If you ever find yourself with so much free space you need reclaimed that VACUUM FULL seems the only way out, you should consider a few things.
First, can you use CLUSTER to rebuild the table? It essentially makes a clean second copy of the table and then substitutes it for the original once finished. While this still requires a long lock and some processing time, this is far more efficient in most cases than VACUUM FULL. Note that CLUSTER is only completely safe for this use as of PostgreSQL 8.3. In earlier versions, a common trick was to use ALTER TABLE in a way that would rewrite the entire table with a new version.
Second, how can you adjust your VACUUM and/or autovacuum strategy to keep this large of problem ...
