I think what happened is the user registered and confirmed his email.
You then got an email telling you that you have a new user to approve, but before you got around to it, that same user changed his email address causing him to come out of moderation and back to email confirmation state.
So when you went to look for him in the moderation queue he was not there. Only once he re-approves his email, will he go back into moderation.
While the user is still on your ACP user list, he's state is "Awaiting email confirmation".
If the user state shows as "Valid" and you did not approve them and never changed the registration parameters, then perhaps you have another add-on that deals with registrations as this add-on does not modify the user state at all.