VACUUM and VACUUM FULL do not return space to OS
First you should at upgrade to the latest version of the 8.3 branch (which is 8.3.17). There were several fixes to VACUUM and autovacuum after the 8.3.3 (although I don't think any of those would fix your problem)

I think there are situations where even VACUUM FULL will no free all space possible. You could try to run CLUSTER on the table which does a better job of rebuilding it than VACUUM FULL (especially with that old version)

The drawback of CLUSTER is that it requires more intermediate space (because rebuilding isn't done "in-place"), so if your filesystem is really full, than it might not be possible.