Sorry - I forgot to mention that I am using PostgreSQL 8.3.9 on Ubuntu 9.04. And just to be clear - I am not suggesting that there is a bug in Postgresql :-) I am just trying to clarify what it does and doesn't do.
It uses VACUUM and not VACUUM FULL, there shouldn't be a need of VACUUM FULL if you have autovacuum enabled with proper thresholds. There can be an odd case where you might have to make auto-vacuum a little more aggressive for a specific table.