When you delete an object, you need to update all objects which use the object_id as their context_id, probably setting it to (What is the default now? -4?). This was discussed a while back, has acs_object.delete been changed to do this yet? Of course you also have rel_segments and permissions to delete as well.
Is the issue with deleting unwanted user records similar and if a solution is worked through to one problem will it be applicable to both issues?