VACUUM FULL achieves nothing / Postgres 7.3.2 + RedHat 7.3

Ladies and gentlemen,

I am running a Postgres 7.3.2 on a Red Hat Linux release 7.3
(Valhalla)
in a multiprocessor (4) environment.

There is a db table in one of the databases containing some 20.000
records updated on a daily basis. When attempting to delete about 4000
deprecated records from it the query ran for almost half an hour and
postmaster occupied 100% CPU, so i decided to cancel it. (Note: select
querys run fine and finish within milliseconds).

In order to reproduce the problem, i copied the above database to my
staging system (same linux, same postgres), and ran a vacuum full
analyze. It finished after 33 minutes. After the vacuum full the
deletion from the 20.000 records table succeeded within 23 ms.

Now, here's the problem:
When running the VACUUM FULL on the live system, it finished after 20
Seconds (without error messages) - and did not change anything.
Performance is still bad, and the delete from xxx where ... still
takes forever.

Additional information:
The applications using the database are java - based and create
persistent connections (from a connection pool) to the postgres
database. These connections  are on autocommit, thus, there should not
be any opened transactions preventing the vacuum full from write -
locking the tables.

Any idea what i am doing wrong? Any help appreciated.

Kind regards,

R. Willmington