I think the problem is that there are 2 similar procs in the membership_rel package.
membership_rel__delete
deletes the entire acs_rel
membership_rel__deleted
simply changes the state of the rel to 'deleted'
The user deletion pages should be calling the second one, but instead they are calling the first one. Simple patch for PG and Oracle (to CVS head) available
here.