Pascal's right - all traces should be removed. Most packages don't use "on delete cascade" so you need to chug around looking for things to delete. Things get missed which is why you see things like dangling permissions.
Judicious use of "on delete cascade/set null" would help with this problem, a lot. I couldn't help but notice that Ian used "on delete" freely in the portals package.
Maybe that's why he got laid off :)
