This shouldn't be too difficult using transport rules.
Am on Exchange 2007 but process is extremely similar...
Restricting outbound internet mail for some users
Create a Distribution Group and add the recipients you want to prevent from sending internet email as members of the group.
Create a Transport Rule
1) Fire up Exchange console | Organization Configuration | Hub Transport | Transport Rules tab | click New Transport Rule
2) Enter a name for the rule – e.g. Rule-NoInternetMail
3) On the Conditions page, select “From a member of a distribution list“
4) In the rule description, click the link for distribution list (underlined)
5) Click Add | Select the distribution list “DG-NoInternetMail”
6) Under Conditions, select a second condition “Sent to users inside or outside the organization“
7) In the rule description, click Inside (underlined) | change scope to Outside
8) Click Next
9) On the Actions page, select “send bounce message to sender with enhanced status code“
10) If you want to modify the text of the bounced message (optional): In the description, click “Delivery not authorized, message refused” | enter new message text
11) Click Next | verify the rule conditions and action in the summary
12) Click New | click Finish
Restricting inbound internet mail for some users
Using the Exchange console:
Expand Recipient Configuration > select recipient > recipient Properties | Mail Flow Settings page | Message Delivery Restrictions | Properties
Select “require that senders are authenticated“
(source: http://exchangepedia.com/2007/07/how-to-prevent-a-user-from-sending-and-receiving-internet-mail.html)
You should set up a receive connector operating on a non-standard port (maybe 2525) and restrict it to only accept IP addresses of servers that you know are allowed to send out.
Create the connector with nothing ticked in Authentication and Anonymous users ticked for permissions groups.
After that you'll need to run the following command in PS as Exchange by default blocks anonymous relaying on any receive connector.
Get-ReceiveConnector “Receive Connector Name” | Add-ADPermission -User “NT AUTHORITY\ANONYMOUS LOGON” -ExtendedRights “Ms-Exch-SMTP-Accept-Any-Recipient”
I just tested this on my own exchange server and managed to send to both gmail and my own domain, sending from the exchange domain as well as a fake domain.
Also add the -port 2525 argument onto your PS script.
Best Answer
What you're trying to do is not sending, it's relaying. The MFPs are sending and they are trying to use your Exchange server as an SMTP relay. Exchange used to be an open relay by default, but that is a major security problem so now Exchange servers will not relay any mail by default. Using Outlook or OWA is not relaying because in those cases the Exchange server itself is generating the message.
This page has instructions on how to create an SMTP relay connector for Exchange 2013. Briefly, you create a new receive connector, allow anonymous connections, and (very important) you specify the IP addresses of your MFPs as allowed to send through that connector.