Outlook Anywhere won't connect after remote mailbox move in Hybrid Deployment

I've successfully run the Hybrid Configuration Wizard in an environment with Exchange 2010 on premises and exchange online.
After it completed I did a remote mailbox move on a test user and found that OWA wouldn't work. Fixed this easily enough by going to EMC, Organization Cinfugration->Organization Relationships, properties, External Organization and adding my email address domains to the "Federated domains of the external Exchange organization". The configuration wizard only had the <domainname>.mail.onmicrosoft.com entry.
After that fix a login to the owa would let the user know the new Exchange Online URL.
I then started Outlook 2013 for the test user, it prompted for credentials, shows trying to connect and then "DISCONNECTED".
Did I miss a step after completing the hybrid configuration wizard? Did it maybe miss another section (like it did for OWA) that I need to manually fix to get Outlook Anywhere to work after the remote mailbox move from on premises to cloud?
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

deanaveyAuthor Commented:
I've also noticed that sending an email to testuser@mydomain.com doesn't get sent onto the cloud from the on premises server either.
deanaveyAuthor Commented:
In fact, it doesn't just fail to deliver to the cloud, it eventually bounces back an NDR that leads me to believe it's sending out the normal send connector instead of the Office 365 send connector that was created during the Hybrid Configuration Wizard:

5.4.6 Hop count exceeded
deanaveyAuthor Commented:
Found out why emails weren't going. I made a mistake when doing a new remote move request to move the users mailbox to the cloud. Where you pick the target delivery domain you are supposed to use "mydomain.mail.onmicrosoft.com". Instead of what I did and picked "mydomain.com". Once I did that now emails are delivered to the on premise server and then sent on to the mailbox in the cloud.
So part of the problem fixed, at least.
deanaveyAuthor Commented:
After the move request was redone with the proper target delivery domain I can now connect from Outlook Anywhere. But emails sent from the cloud user to other users on the same domain, but still located on premises, fail:

The email address you entered couldn't be found. Please check the recipient's email address and try to resend the message. If the problem continues, please contact your helpdesk.

It appears that it's not using the "hybrid mail flow outbound connector" that was created by the hybrid configuration wizard.
Any ideas on how to fix this part?
deanaveyAuthor Commented:
There was another issue, one I thought was unrelated, where some of the accounts created in the cloud via DirSync already had mailboxes in the cloud so those users could not have their mailboxes moved from on premise to cloud. To correct that I:
1. Deactivated active directory synchronization from the cloud portal and wait for it to finish
(I noticed that deleted users still showed if they were licensed when they were deleted. So before deleting all users I deselected Exchange Online LIcenses for each one. Probably not needed when you force deletion of all deleted items but I did it anyway)
2. Deleted all cloud user accounts that were created by DirSync
3. Deleted all the security groups as well
4. Emptied the deleted users items with this command:
Get-MsolUser -ReturnDeletedUsers | Remove-MsolUser –RemoveFromRecycleBin –Force
(found here: http://365command.com/justins-tech-tip-of-the-week-purging-and-removing-deleted-users-and-mailboxes-from-office-365/)
5. Activate directory sync from the cloud (and wait for it to finish)
6. Went to my on premise DirSync server and ran the Directory Sync Configuration again. I think this is needed when you deactivate from the cloud, and reactivate, in order to turn on password sync option again. Otherwise it just syncs the accounts and not the passwords)

After that I did a remote mailbox move for a test account and was able to send and receive from my cloud account to an on premises account.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Office 365

From novice to tech pro — start learning today.