Found the solution. ECP Config Exchange Server was pointing to a wrong "InternalUrl".
Fix
Set-EcpVirtualDirectory -Identity "SERVERNAME\ecp (Default Web Site)" -InternalUrl https://SERVERNAME.domain.com/ecp
Outlook Clients start contacting the right URL after a bit of time, though you can force it by deleting the XML files with "Autodiscover" in their name under %LOCALAPPDATA%\Microsoft\Outlook
Outlook will automatically recreate those XML files.