Kaspersky endpoint security 8 with Remote Desktop
Nmap reported port 3389 was filtered but Windows Firewall was disabled. It turns out that Kaspersky Endpoint Security 8 (which was installed) does have its own Firewall, which was activated in my setup, and apparently does not care whether you activate Remote Desktop in Windows or not. You have to go to its management app: Configuration/Antivirus protection/Firewall and click the packet filtering rules to enable TCP port 3389. I wish they either warn you when they see Remote Desktop is activated and there is a rule preventing it to work or to just self-adjust to that change.
But it is clear that Antivirus software real task is just make the life of Windows users miserable, isn't it?