How did you remove that permission? Did you use the PowerShell command (Exchange Management Shell) or the Exchange Management Console GUI?
As mentioned in the article you posted you have to use PowerShell to alter just one specific permission, but not all anonymous connections, or else you'll end up accepting no external mails at all.
So you can't do that with the Exchange Management Console (with unchecking "Anonymous users" in the "Permission Groups" tab) but instead use the PowerShell command to remove just Anonymous Logon from the ms-exch-smtp-accept-authoritative-domain-sender
permission.
That setting defines which senders are allowed to send from an authoritative domain of your Exchange server. So, if you remove Anonymous Logon from that permission, an unauthenticated user is not allowed to send a mail from your Exchange server's authoritative domain.
I don't have an Exchange Server here to test that right now, so I'll assume that the article on exchangepedia is accurate.
As always, check, test and double check your server settings after tampering with mail sending permissions, so you can be sure you don't have created an open relay. I.e. try connecting to the SMTP server with telnet from inside and outside your network to check if it accepts an unauthenticated mail.