Really helpful article, thanks for sharing.
But why doesn't the Tailspin OnPrem Exchange server return the target address to Contoso? In that case, I won't need to sync mailboxes with target address from Tailspin to Contoso.
Scenario:
Contoso user asks for F/B of cloud user "userA@tailspintoys.com" -> Contoso Exchange asks Tailspin Exchange -> Tailspin Exchange recognizes, that "userA@tailspintoys.com" has a target address with "userA@tailspintoys.mail.onmicrosoft.com" and provide this information to Contoso Exchange. Contoso Exchange will start / redirect F/B request against O365 (of course you need to configure the OrganizationRelationship from Contoso to tailspintoys.mail.onmicrosoft.com first).
This would be my desired scenario.