As per @Vasil Michev's suggestions, you should double check that the Custom Domain is registered in the tenant, and of course that you are specifying the proxyAddresses in the correct format.
Although technically the article you referenced should work, it's making some assumptions about other attributes that should be present.
If you are using Exchange Online and syncing your local AD, the only *supported* way (that's to say other solutions like editing using ADSIEDIT can work, but it's not tested or supported by Microsoft) is to use the free Hybrid Exchange server licence to install a copy of Exchange Hybrid as a "management server" for those attributes. Whilst Microsoft is working to eliminate this need, at the moment, that's the best way of ensuring you can manage all those attributes correctly and have all the correct schema updates present to syncronize Hybrid attributes.
This article on Technet details this requirement. The relevant statement is below:
"The question of whether a third-party management tool or ADSIEDIT can be used is often asked. The answer is you can use them, but they are not supported. The Exchange Management Console, the Exchange Administration Center (EAC), and the Exchange Management Shell are the only supported tools that are available to manage Exchange recipients and objects. If you decide to use third-party management tools, it would be at your own risk. Third-party management tools often work fine, but Microsoft does not validate these tools."
I would suggest that if you are relying on third-party blogs to work out how to add aliases, you may be better making sure you have things set up the "supported" way. Yes, there are other customers out there who do without happily, but they often have some seasoned Exchange admins or identity specialists ready to provide support in case it all goes wrong.
In the short term, I'd follow those suggestions for a delta sync, and double check proxyAddresses looks similar to:
SMTP:alias@primarydomain.com
smtp:alias@secondarydomain.com
However there are a variety of other attributes you would expect to see on one the local AD will usually have defined as what Exchange Hybrid calls a "Remote Mailbox".
Steve
