Try this article from RIM: BlackBerry Search Results
Essentially the 5302 error means that 1 of the 2 MAPI reg keys are named wrong or are missing.
Is this a new install? Did you move to new hardware. What has changed recently.
Also, the last error you posted measn that the Messaging reached the maximum amout of restarts and now you have to wait 24 hours or reboot the BES.
But until you fix the reigstry it will continue to fail, fix the reg key and then reboot.
Let us know if you have any questions.