Spam from mail, it is not at all clear where to start and what to do?

Question

Malware

Good day. Two months ago I came to a new company, I didn’t get to meet the previous administrator personally, he got a lot of problems, such as lagging equipment, a mess, the absence of 50% of passwords, year-long hangs. Now I'm struggling with the following:
So, there was a non-delegated domain, exchange 13, no spam cutters, no dkim / spf records were in sight, on Google / mail / Yandex, our letters simply went into spam or got into spam.
Set up dkim / spf, got out of spam. But the primary source of troubles with the mail has not gone anywhere - there is no open relay, but spam comes from the domain, it turns out that there is a virus somewhere. Servers on esxi, about 20 pieces, half of Windows, half of Unix. Ekschendzh looked by means of cureit, everything is pure.
Actually, the question is: what to do? in which direction to dig, where to start in order to find the source of problems? Reset user passwords? scan all servers for malware?
Now I'm interrupted by the transport rule, "if OUTSIDE the domain but in the departure address there is %@domain_name% then drop it.

Answer 1

hello, look at the email headers and server logs. this usually answers 99% of the time.

Answer 2

Deny outgoing smtp 25 on the gateway, open only on the Exchange IP Address, configure logging of any connection on the 25th port from the local network to the outside. Localize malware on infected computers.
Exchange check for Application Relay (anonymous Receive connector - authenticates by IP - Audit who owns IP, enable Verbose logging, see smtp sessions who sends - use Powershell for analysis, or LogParser, detect malware service / server - neutralize).