Has anyone run into a problem setting up scan-to-email which is caused by security settings on their email server?

If this is a local (in-house) smtp server their admin may have to specify the scanner IP as allowed to relay.

Some admins require only specific IP's are allowed to relay to prevent a mailbot application on a workstation from relaying out through it and broadcasting spam.

Related Question: We are trying to set up scan to email on a network comprised of Mac's 10.4 & 10.5. Since we couldn't get it to work with their email server, we created an email on our SMTP server and tried to configure scan to email again. Kept getting SMTP server error messages. Any ideas??

The fundamental question with SMTP is what happens with your service laptop configured as a substitute for the scan system.
Disconnect the scan system, set your laptop as the same IP as the scan system and telnet into the mail server from a command prompt:

Telnet smtp.server.com 25

You should get a banner that starts with '220'

It is actually possible to construct a test email completely from the command line and send it. It's nice to be able to do it this way, because you can really see what the SMTP server has to say about what you're trying to do - ie - relaying denied, invalid user, invalid password, connection refused, etc.

If it works from the command line it is very highly likely it will work from the MFP.

It is also important to note that if you are doing this on your shop network, your laptop may already be a part of that network and 'friends' with the SMTP server (Relaying can be allowed to domain members and rejected to all others - like the MFP) - but the IT guy for your shop should already know that.

Here are some instructions from Microsoft Technet - they're a little more than is necessary to do a basic test, but it pretty much covers all the bases:

Note:
You should always use a valid sender e-mail address so that any non-delivery report (NDR) messages that are generated by the destination SMTP server are delivered to the sender of the message.
To use Telnet on port 25 to test SMTP communication
At a command prompt, type telnet, and then press ENTER. This command opens the Telnet session.

Type set localecho and then press ENTER. This optional command lets you view the characters as you type them. This setting may be required for some SMTP servers.

Type set logfile <filename>. This optional command enables logging of the Telnet session to the specified log file. If you only specify a file name, the location of the log file is the current working directory. If you specify a path and a file name, the path must be local to the computer. Both the path and the file name that you specify must be entered in the Microsoft DOS 8.3 format. The path that you specify must already exist. If you specify a log file that doesn't exist, it will be created for you.

Type open mail1.fabrikam.com 25 and then press ENTER.

Type EHLO contoso.com and then press ENTER.

Type MAIL FROM:chris@contoso.com and then press ENTER.

Type RCPT TO:kate@fabrikam.com NOTIFY=success,failure and then press ENTER. The optional NOTIFY command defines the particular delivery status notification (DSN) messages that the destination SMTP server must provide to the sender. DSN messages are defined in RFC 1891. In this case, you are requesting a DSN message for successful or failed message delivery.

Type DATA and then press ENTER. You will receive a response that resembles the following:

354 Start mail input; end with <CLRF>.<CLRF>
Type Subject: Test from Contoso and then press ENTER.

Press ENTER. RFC 2822 requires a blank line between the Subject: header field and the message body.

Type This is a test message and then press ENTER.

Press ENTER, type a period ( . ) and then press ENTER. You will receive a response that resembles the following:

250 2.6.0 <GUID> Queued mail for delivery
To disconnect from the destination SMTP server, type QUIT and then press ENTER. You will receive a response that resembles the following:

221 2.0.0 Service closing transmission channel
To close the Telnet session, type quit and then press ENTER.

If it's an issue with authentication, I've had to put the username and password in 2 different places on the NS-30 web interface before it logged into the email server correctly.