This has happened to us before, there are two things you need to check:
1. Server Space, if the space is low, the Exchange Server services stop without any warning. Free up some space and then restart the services.
2. If you have enough space, restart all Microsoft Exchange Services.
Worst case, restart your server.
Hope this helps. Suresh Mukhi