I ran into this problem. I thought I'd go into a little more detail in case someone else comes across this. You need to add the IP address or the range of IP addresses to the relay restrictions and grant them access.
I'm working to test scan to email on a newly installed 7556 and it gives an error of "Failed: One or more of the addresses are invalid. No messages were sent"--only when sending to OUTSIDE email addresses--ones that are not on the same domain as the outbound email address. Internal emails within this domain send just fine.
It is my understanding this is normally an issue on the SMTP server and/or Firewall having to do with relays. Are there any other potential causes to this problem?