First, while vacuum is usually preferred to vacuum full, in this case, I usually find that vacuum full clears up enough cruft to be worth it (not always, but especially if you are also having performance issues).
IIRC, vacuum full was pretty broken in 8.1, which the output the original postered showed indicated they were running.
I certainly wouldn't recommend it for routine maintenance. The problem I have run into is that sometimes folks don't vacuum db's and you find this out after 7 years of write-heavy workloads..... In this case, there aren't a lot of great options. In 8.1 a normal vacuum will usually lead to tons of bloat in this case because the FSM isn't big enough to accommodate all the free space which is a problem. So at that point, vacuum without the full option is pretty broken in 8.1 :-P I often find in those cases it is a choice between vacuum full and dumpall/initdb/reload/analyze..... It is better now that there is no maximum size for the free space map though.
Best Wishes,
Chris travers
-- john r pierce 37N 122W somewhere on the middle of the left coast