I'm guessing that your rooted since he/she used Titanium BU to delete them...?
You will need the messaging.apk file and will have to install it through Root Explorer by going to system/apps.
Older apk files located here>>>
http://www.chadhaney.com/droidXDefault/516/
Newer ones here>>>
Free File Hosting Made Simple - MediaFire
Just download them to comp and unzip into folder.
Instructions for adding apk's>>>
-Place the apk(s) of the apps on your sdcard.
-Use your chosen means to copy the apk(s) to /system/app (this will require making /system/app writable. In Root Manager just press the R/W key when you're exploring /system/app).
-Click on the apk once it's in /system/app and install it.
-Now, you've installed the program, but the system won't see it as a system app unless you change it's permissions. In Root Manager, long press on the app (in /system/app) and click on "permissions". Then make sure that only the following boxes are clicked: User Read, User Write, Group Read, Others Read.
-Make sure you make /system/app read only again by clicking that box in the top right while you're exploring the folder.
-Reboot phone.