Optimizing DELETE

I've just fired off a "DELETE FROM table" command (i.e. unfiltered
DELETE) on a trivially small table but with many foreign key references
(on similar-sized tables), and I'm waiting for it to finish. It's been
10 minutes now, which seems very excessive for a table of 9000 rows on a
3 GHz desktop machine.

'top' says it's all spent in USER time, and there's a ~~500KB/s write
rate going on. Just before this DELETE, I've deleted data from a larger
table (50000 rows) using the same method and it finished in couple of
seconds - maybe it's a PostgreSQL bug?

My question is: assuming it's not a bug, how to optimize DELETEs?
Increasing work_mem maybe?

(I'm using PostgreSQL 8.1.4 on FreeBSD 6- amd64)

(I know about TRUNCATE; I need those foreign key references to cascade)