It came to my attention recently and after pratting about with Exchange ActivSync on iPhones and a Blackberry chappie expecting the SMT's Blackberries to just work with our exchange server that something was amiss (the clue there was that "if the email client isn't on then then the blackberry can get the message").

Ah hah. POP! Ah hah! IMAP.

Anyway, turns out the IMAP VS never starts properly after the server reboots unless you tell, by means of editing the registry, the server to wait a bit longer to discover the domain topology. I suppose that while we think of the IMAP VS as serving the internet, it also needs to serve the local domain and if that doesn't exist you can't really blame it for giving up.

XADM: Exchange 2000 Services Do Not Start and a "0x80040a01" Error Message Is Logged - had the answer for me.