Since you don't have enough space to run a vacumm or rebuild, you can always rebuild your postgresql databases by restoring them. Restoring the databases, tables, indexes will free up space and defragment. Afterwards, you can setup automated maintenance to vacumm your databases on a regular basis.
1 Backup all of the databases on your postgresql server
You will want to backup all of your databases to a partition that has enough space. If you were on Linux, you can use gzip to further compress the backup to save space
su - postgres
pg_dumpall | gzip -9 > /some/partition/all.dbs.out.gz
2 Backup your configuration files
cp /path/to/postgresql/data_directory/*.conf /some/partition/
3 Stop Postgresql
pg_ctl -D /path/to/postgresql/data_directory stop
4 erase the contents of the data directory
rm -Rf /path/to/postgresql/data_directory/*
5 Run initdb to reinitalize your data directory
initdb -D /path/to/postgresql/data_directory
6 Restore configuration files
cp /some/partition/*.conf /path/to/postgresql/data_directory/*.conf
7 Start Postgresql
pg_ctl -D /path/to/postgresql/data_directory start
8 Restore the dump of all the databases you made
gunzip /some/partition/all.dbs.out.gz
psql -f /some/partition/all.dbs.out
Best Answer
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.