Hmmm ... not sure what's going on there. I have no problems at all adding users with the same emails or usernames as accounts who have been deleted.
When users are deleted, the "deleted" flag is turned on, but the username is also set to the email address, and the email address is set to empty. This frees up both the username and email address to be used by new users.
I did however just notice a potential problem with deleting a user (with a particular email address) for the second time, in that the username (which is the primary key) might already exist. I've just made a small fix in admin/user.php for that case.
Cheers,
Martin