Where did you remove it - from the dock or from the /Applications folder.
if its from the folder then the application has been physically removed from the computer. It may still be around though if you did not clean out the trash. Look there and drag it back to /Applications if its in the trash
That is strange. Does that mean, going to the Applications folder on that user account via Finder > CMD+SHIFT+A Mail does not show up, but when you login to another account, Mail is still there when going to Finder > CMD+SHIFT+A?