delete hung soon after vacuum verbose analyse
I'm not able to test this since I don't use postgresql 8.4 but i think you have to:




check which transaction(check Sql statement) is locked and which is locking.

to check it



SELECT 
    kl.pid as blocking_pid,
    ka.usename as blocking_user,
    ka.current_query as blocking_query,
    bl.pid as blocked_pid,
    a.usename as blocked_user, 
    a.current_query as blocked_query, 
    to_char(age(now(), a.query_start),'HH24h:MIm:SSs') as age
FROM pg_catalog.pg_locks bl
    JOIN pg_catalog.pg_stat_activity a 
        ON bl.pid = a.procpid
    JOIN pg_catalog.pg_locks kl 
        ON bl.locktype = kl.locktype
        and bl.database is not distinct from kl.database
        and bl.relation is not distinct from kl.relation
        and bl.page is not distinct from kl.page
        and bl.tuple is not distinct from kl.tuple
        and bl.virtualxid is not distinct from kl.virtualxid
        and bl.transactionid is not distinct from kl.transactionid
        and bl.classid is not distinct from kl.classid
        and bl.objid is not distinct from kl.objid
        and bl.objsubid is not distinct from kl.objsubid
        and bl.pid  kl.pid 
    JOIN pg_catalog.pg_stat_activity ka 
        ON kl.pid = ka.procpid
WHERE kl.granted and not bl.granted
ORDER BY a.query_start;




Note:this is for postgresql v9.1 i am not sure this work for 8.4 or not.


You mentioned about dead lock so it mean your transaction are waiting each other until occur deadlock(no transaction completed(commit or rollback) so make sure the locking transaction was completed(process 12729) and then transaction (Process 12800) will not wait anymore.
Vacuum is occur table lock level too. when u run vacuum command it will locked the target tables to reclaims storage occupied by dead tuples so that why when you check the df - your free disk space is higher than before.
about Privileges



WARNING:  skipping "pg_authid" --- only superuser can vacuum it
WARNING:  skipping "pg_database" --- only superuser can vacuum it
WARNING:  skipping "pg_tablespace" --- only superuser can vacuum it
WARNING:  skipping "pg_pltemplate" --- only superuser can vacuum it
WARNING:  skipping "pg_shdepend" --- only superuser can vacuum it
WARNING:  skipping "pg_shdescription" --- only superuser can vacuum it
WARNING:  skipping "pg_auth_members" --- only superuser can vacuum it


you need to use supper user(postgres) to make vacuum verbose analyse for above tables (pg_*) or you just specified the target table only, it no need to use supper user privileges.

ex:

vacuum verbose analyse [table_name];