I recently upgrade to the new 4.5 OS and it deleted my BB Messenger. I went to re-download the application and it gave me this message:
Sorry, your device does not meet the system requirements that are needed to support Blackberry Messenger for Software Versions 4.0 and 4.1
There have not been any reports of BlackBerry Messenger being removed from the device OS package.
First place to check, Options / Advanced / Applications. BlackBerry Messenger should be in the list.
Second, Application Loader as Garz suggested. BlackBerry Messenger should be between BlackBerry MDS Runtime and BlackBerry S/MIME support. If it is not there, something strange is going on.
Final check, use Windows Computer. Open the drive C:\ icon and navigate too:
C:\program files\common files\research in motion\shared\loader files\device package\java.
Verify the two files, net_rim_bb_qm_peer.cod and net_rim_bb_qm_peer_resource.cod are present.