What would cause this to happen? Anything internally works fine, but if we try to scan to an external company email address (or a gmail address, etc.) the scan fails and says the email address is invalid?
Most likely a relay needs to be set on the mail server for the device, without knowing tha mail server in question I can't help with that.
There are also mail servers that do not allow a relay, there is no working around that.
For instance gmail has aspmx.l.google.com and Office365 has Direct send.
Then there are printers with options to disable sending outside the domain (For security mostly, IT dept would set this in a Confidential environment usually)
For instance a Connectkey would be Properties > Services > Email > Setup > Security