We have On-Premises Exchange 2013 servers in ourenvironment.

What we have been experiencing lately is that when we manually add additional alias's to distribution groups or mailboxes, it can take 24-48+ hours before an external email can send to the new alias smtp address. We have no problem sending them to the new alias internally though. Its just a matter of time, then it works all of a sudden. 

After adding the alias to the DG or mailbox, I run the Get-Mailbox -identity identity | FL which shows me the alias is correctly added.  

Our mail is routing thru Microsoft Exchange Online Protection for AntiSpam, theres no DirSync in between as we are totally on premises except mail comes thru EOP. 

What could be causing these delays? 

You don't synchronize directories with EOP?  That's often done to block mail for nonexistent recipients.  You might want to recheck that, because it could easily explain delays you're seeing.

Hi Viva,

Thank you for your question.

In addition, Microsoft Exchange Online Protection (EOP) is a cloud-based email filtering service that helps protect our organization against spam and malware, and includes features to safeguard our organization from messaging-policy violations. EOP can simplify the management of your messaging environment and alleviate many of the burdens that come with maintaining on-premises hardware and software.

We could refer to the following link:

https://technet.microsoft.com/en-us/library/jj723119(v=exchg.150).aspx?f=255&mspperror=-2147217396

If there are any questions regarding this issue, please be free to let me know.

Best Regard,

Jim