You are correct that delete means something different than you would assume. As I understand dotlrn and use it, you can put users into 2 inactive states: deleted and banned. "Deleted" means that an account is inactive BUT the user can reactivate that account when they try logging in again. "Banned" means that they cannot get in and will get a very inelegant message when they try (you've been banned). The third non-state of existence for users is "nuked" BUT you can only use this if they have never logged in and/or made any contributions to the system, so I only use it/can use it successfully with those external folks who have self-registered and whose accounts I don't want to approve for access. Nuked users go away altogether; banned and deleted users do not.
A couple other things: 1) a banned user who is an admin of a group will still receive "request to join" emails (clearly a bug, at least for us at Sloan); to prevent this, remove the user from their groups and then ban them; 2) on the /admin/users page, there is a User Type called "Deactivated" but there is no display page for this group, so if you want to look up a deactivated user, you have do a quick search for them; 3) if you can't nuke someone who's listed as a pending user on the /admin/users page, try approving them and then nuking them - sometimes that works.
Hope this info is useful to you.