Generally the issue your running into is caused by something called "Access Control" on your exchange server. This setting on your exchange server tells the mail server what should have access to transmit information through your own internal network. You may just have to add that printers IP or MAC address to the Access Control settings for it to allow the device to send internal traffic.
The other side of these restrictions is called "Relay Restrictions", relay restrictions would prevent the same type of traffic but only to external networks..Obviously this part is configured correctly if you are able to scan to external sources.
