Out Of Office "server is unavailable" "Outlook 2010 connecting to Office 365"

Hi,

I have moved my companies mail from a locally hosted Exchange 2007 environment to a Office 365 environment. All users can pick up the mail no probs and everything seems to be working fine apart from "Out Of Office" which periodically fails, giving users a "Server is unavailable" message when they try setting up OOO, I have loaded all the latest Office 2010 patches etc and have recreated the local mailboxes, which seemed to cure the problem for a few weeks, but now the issue is back again for some random users?

I havent retired the old exchange environment from the network as yet, and as such the users get a certificate message when they open up outlook which relates to the old server. this doesn't seem to cause an issues with them pickup up mail etc, but i am not sure if this is whats causing the issue. Not all users are suffering the problem at the same time, it seems rather random.

Has anyone experianced this issue, and could you shed some light on what might be causing it?

Many thanks