Here is the error report:
Error:
Global updates need to be made to Active Directory, and this user account isn't a member of the 'Enterprise Admins' group.
For more information, visit: http:/
Error:
You must be a member of the 'Organization Management' role group or a member of the 'Enterprise Admins' group to continue.
For more information, visit: http:/
Error:
You must use an account that's a member of the Organization Management role group to install or upgrade the first Mailbox server role in the topology.
For more information, visit: http:/
Error:
You must use an account that's a member of the Organization Management role group to install the first Client Access server role in the topology.
For more information, visit: http:/
Error:
You must use an account that's a member of the Organization Management role group to install the first Client Access server role in the topology.
For more information, visit: http:/
Error:
You must use an account that's a member of the Organization Management role group to install or upgrade the first Mailbox server role in the topology.
For more information, visit: http:/
Error:
You must use an account that's a member of the Organization Management role group to install or upgrade the first Client Access server role in the topology.
For more information, visit: http:/
Error:
You must use an account that's a member of the Organization Management role group to install the first Mailbox server role in the topology.
For more information, visit: http:/
Error:
Setup encountered a problem while validating the state of Active Directory: Couldn't find the Enterprise Organization container.
For more information, visit: http:/
Error:
The forest functional level of the current Active Directory forest is not Windows Server 2003 native or later. To install Exchange Server 2013, the forest functional level must be at least Windows Server 2003 native.
For more information, visit: http:/
Error:
Either Active Directory doesn't exist, or it can't be contacted.
For more information, visit: http:/
Warning:
Setup will prepare the organization for Exchange 2013 by using 'Setup /PrepareAD'. No Exchange 2010 server roles have been detected in this topology. After this operation, you will not be able to install any Exchange 2010 servers.
For more information, visit: http:/
Obviously, the AD was prepared previously (having a working Exchange 2013) and I'm a Schema and Enterprise Admin.
Solution:
It turned out that I was trying to install the Exchange in site A (a site with a working DC) but the the Schema Master FSMO role holder DC was located in site B. Of course both was perfectly connected and replicating with the other. However, for whatever reason my clever Exchange setup was simply unable to connect the Schema Master and exited in such a stupid way. I moved the Schema Master role to site A and voila, Exchange setup immediately worked.