I dont think that the problem is in the operating system /with the Exchange Mail box.The system may be infected / attacked with unknown virus.
You have not mentioned about the firewall infrastructure.If installed, what is the firewall make? (Software / Hardware)
Update your server with online Microsoft updates & check with different Antivirus Softwares.
Update me the status to firstname.lastname@example.org