Two things.
First, users cannot have their account "deleted." Users exist always and forever. I suspect that the user was "recycled" (the details of the original user were overwritten with the new user), and the old user's settings are still hanging out in Setup. For this reason, it is absolutely vital that you never recycle users.
Second, the Send Notification Email can't be configured. It always behaves the same way. The current user is the sender of the email, using a predefined template that cannot be modified.
My guess is that the email is the personal settings for the user (Your Name > Settings/My Settings > Email > My Email Settings). You can configure your display name and email address here, which may be different than the First Name, Last Name, and Email address of the user.
In the future, do not recycle users. The system only counts active users against your license count, so there's no legitimate reason for changing a user this way.