I've done what the article says and more.
Only recipient validation is enabled to be able to use the "Reject Invalid Recipients" feature for all the mail servers (Lotus Notes). And only one of three mail servers is enabled for email authentication at the moment.
I'm still not sure which is causing the problem of SBG not sending the emails - either the Address Resolution or having multiple LDAPs. I've disabled the Control Center Authentication based on the Administrator guide stating that it is used by clients to access the quarantine folder and we don't allow the clients to access that in the first place.
I've also disabled the address resolution.
Everything's working, so far.