It's still installed. Pull up the application drawer, scroll to Corporate Email, long press it, and you will be able to place it on any home screen you like. No worries. You just deleted a shortcut, not the underlying application.
I agree. Try a restart. Folks have had to go to (relatively) extreme measures to delete that application and, since it sounds like you are just setting up your phone, I doubt you've gone that route (rooting the device, etc., etc.).