Messages is a stock iOS app that can't be deleted unless you're jailbroken. It's probably stuck in a folder or something. Try a hard reset (hold the power button and home button down until you see the Apple boot logo). Otherwise you'l have to restore your phone.