did you root? It shouldnt be possible without root.

You can reinstall it from an apk... You could download any custom ROM (so long as its samsung based) and extract the system/app/secemail.apk and install it like any other app.

 

Then if you don't want to factory reset you could just try installing it as above

 

Instead of being uninstalled, could you have possibly disabled the app? This would prevent the app from showing in your app drawer. If so then just go into Settings, Application Manager, All, then scroll ALL the way down to the bottom to find it. Click it and press Enable.