Exchange 2010 sends out spam

Since you already tried the open relay tests from the internet, that means it's a computer on the internal network sending spam. It's most likely a compromised machine with a virus on it, so that needs addressing as a matter of urgency as well.

It sounds to me like you have a Receive Connector which is set up to allow open relaying from inside the network (which is why the external tests didn't pick it up).

The message tracking logs should tell you what Receive Connector the mails are being received through, so you'll need to look at the properties of that Receive Connector and make them more restrictive. Use the command Get-MessageTrackingLog -MessageId "<<Spam Message ID>>" |ft MessageId, ConnectorId in the Exchange Management Shell to give you the Receive Connector it's going through.

My guess is your receive connector is set to accept mail from the whole of your internal network (for example 10.1.1.1 to 10.255.255.255) rather than specific IP addresses that need to send unauthenticated email.

Standard practice is to leave the Receive Connector that was created when you installed Exchange as it is and create a new Receive Connector (for example "Allow Anonymous Relay") with the following settings.

• On the Network tab, Listen on all available IP addresses on port 25
• On the Network tab, Add any IP addresses which need to send unauthenticated mail (printers, web servers, monitoring software etc)
• On the Authentication tab, untick everything except Externally Secured (for example, with IPSec)
• On the Permission Groups tab, untick everything except Exchange Servers

Edit: Sorry! On the very last line I said untick everything except Anynymous users - I really meant untick everything except Exchange Servers. My bad :'(

If your relaying configuration is correct, and you're not configured as an open relay, it's most likely one of the following things:

1. A compromised user account is connecting to your publicly-accessible SMTP service, authenticating, and sending spam
2. A server on your network authorized to relay unauthenticated through Exchange is compromised, and sending spam through your Exchange servers
3. As above, but with a desktop machine

In any case, you want to be checking your Delivery Reports for the destination address on that email, which should give you both the sending user and the originating system for the message.