Viviana, when you are saying that you've checked the Active Directory Sites, Subnets & Site-Links and that your DMZ subnet is present and properly configured?
See Step-By-Step: Setting Up Active Directory Sites, Subnets & Site-Links – CANITPRO
When you are using Static Automatic NAT in the Exchange object's properties, please make sure that there are no proxy ARP remnants lurking in the configuration from your manual NAT configs.
Verify that there are no manual NAT rules superseding Automatic NAT rules that could affect traffic TO or FROM exchange in either direction and for any protocol.
Sorry for asking the obvious, but have you tested any other communication from inside to and from Exchange, such as RDP, for instance?
Additionally, what blades do you have enabled on your gateway?
If you have Application Control enabled, you may have to configure explicit rule for communication between Exchange and AD, especially, if you have AppC as the inline Layer with Implicit Cleanup Action Drop.
Do you log everything that you are dropping as well as Implied rules?
if not, you may be missing some clues.
One more thing, and I know it is pretty vague, but what is the situation with IPv6?
Do you have it enabled on Exchange, DCs and on Check Point Gateway?
I believe it must be, for the proper functionality of a good chunk of MS services and is a requirement of MS.
How exactly its behavior changes, if at all, when you are flipping between hide and static of IPv4, I am uncertain, but it may be one more place that you'll have to look at.