RDP connection problem?

Question

Malware

Colleagues, tell me, please!
The problem appeared the other day.
Most clients began to complain that they could not connect via RDP to the server. And not all, someone slips, and someone has "Connection Refused". We thought it was another update, but for some clients the server had not been updated since 2013, and the suspicion immediately disappeared.
The problem was studied from all sides, starting from roles, services, a gateway for connection and everything that follows. Everything is fine, but the problem persists.
They began to sin on the firewall, brandmaur, casper and others, but disabling the above did not help either.
The only solution that helped was changing the connection port.
Who faced the same problem, tell me, eh?
Antivirs do not say anything, only "brazenly eat")

Answer 1

Not enough data to pinpoint the problem.
The first thing that came to mind:
There is probably another host with the same IP as the server, or if you use FQDN to connect, then the DNS records may have doubled. As a result, some clients end up in the wrong place where they are "asked".

Answer 2

Spetros : The server version is basically Windows Server 2008 R2.
Of the software, it costs 1C, so nothing special.
DNS is used by default, which is provided by the data center.
Licensing SPLA, on each server differently, from 20 to 50 licenses.
Connect via internet without vpn.
It also does not connect locally.
Sergey Pisarenko : The option with IP addresses disappears, since there are different data centers, and IP is assigned accordingly for each one, i.e. It's not all happening on the same network.