Exchange 2013 OOF not working for migrated accounts

We are having a problem with the Out of Office responses in Exchange 2013. We are getting the error “Your automatic reply settings cannot be displayed because the server is currently unavailable. Try again later.” I have been through several help articles that I found on the internet and so far none have resolved the problem. Autodiscover is working as expected when connecting an Outlook client – and I can access the url identified by the “Test Email AutoConfiguration” tool for OOF – it returns the xml document as expected. New accounts created in this domain work, but the problem occurs accounts that were migrated from Server 2003 domain running Exchange 2007. I can also access the OOF settings for a migrated account using OWA. The new domain is 2012 and Exchange 2013 and accounts are being migrated using ADMT through a trust, which is working as expected. Only the accounts have been migrated (not mailboxes) and I am not planning to connect the old exchange to the new to do mailbox moves – instead I am just planning to export psts from the old Exchange 2007 server and then import them to the 2013 server. The client dns settings are correct and all other connectivity seems fine. Any ideas are greatly appreciated.

Thanks in advance for any help.

Update- additional info:

Ok, well this is getting a little bit weirder now. Some of the pcs have been migrated to the new domain, but ALL are still accessing e-mail using the Exchange 2007 server in the old domain. This has been working fine for a couple weeks, but now I have starting working with the new Exchange 2013 server in the new domain and there are a couple client computers that are somehow resolving email addresses in the address book of the new server (and should not) and then sending to the old server (which they should). I know this because some of the messages are bouncing and the email address specified in the bounce message matches the LegacyDN attribute pulled from the NEW domain. So it seems somehow Outlook is populating the address book of users connected to the mail server on the old domain even though the Outlook profiles are connected to the old domain/exchange server.