After looking into the issue, I found that legacy Cross-Forest configuration remained in configuration partition from a previous Cross-Forest Exchange Migration. This is located under the Configuration --> Services --> Microsoft Exchange Autodiscover.
Simply remove the additional references to the legacy forest (the ones highlighted in yellow above).
Do not remove "Microsoft Exchange Online". This is a default entry and is used when you create a Hybrid deployment with Office 365.