Here's a random question... How often do you have to reboot your server? I have noticed that over the last few months I have had to reboot the server more often than not to get the devices to talk to the server...

Mail Platform?
Any other reboots in your environment around this time?

I'm guessing Exchange, so in your app log do you have any threadpool errors? What are your ping times to your remote exchange servers. (especially if you have added remote users recently.)

We are using Exchange. No other reboots in the environment. I am getting a lot of error logs on the server concerning blackberries. The ping times are within normal ranges.

Maybe you can post some samples of the errors?

My experience is:

Domino: Never unless installing SP or HF

Exchange: Whenever there is a MS Patch, a number in the Date, a device being used, a letter Y in the Day etc etc

i rarely reboot mine... only when i install a new app..

Here are my example:
1.) I have user x who hasn't contacted in 1 hour. X has 5 pending messages in the queue. Only way I know to jump start those messages is to either restart services or reboot server.

This happens more often. What I also notice is that my times between contact will go from 1-2 minutes between each one and 20-50 minutes between each time... strangeness.

Just now I had the same type of problem. 20 minutes, 3 or 4 messages in pending. Stopped the router service. restarted it and now everything is back to normal.