PostgreSQL returns free space to the operating system for a table when a) the free space is at the very end of the table, and b) it can obtain an exclusive lock on the table. VACUUM FULL tries to force both of these things to happen, but there's probably a dozen bugs in this area fixed by later 8.3 versions that you might be hitting on 8.3.3.
Note that disk space is taken up by both tables and indexes here, and VACUUM FULL is known to increase index size while it tries to shrink table size. Use a query like the ones at Disk Usage to see where the distribution of space is at. If it's actually indexes that are using the space up, no amount of VACUUM will fix things; try REINDEX on them instead. That will need some more space to hold the rebuilt version. If really stuck for space, you might have to drop an index temporary and then recreate it instead. CLUSTER will completely rebuild the whole table and toss out all of the old cruft, but it needs to be able to hold a whole new copy of the table and all indexes to do it.