Unable to receive email from people using Lotus Notes

I did a quick check and, indeed, the response from RCPT TO command takes a bit longer then usual when connecting to your server (mostly when user is not in your directory).
It is not DNS or SPF issue.
I would check your GCs performance to see why lookup takes a bit of long time. Also, do you have anything unusual in your recipient policies?

I checked my recipient policies - just the default settings there.

I don't mean to sound ignorant, but what do you mean by "check your GCs performance "?

Do you think there would be a DNS resolving issue between the 2 servers when an email is sent?

The delay seems to happened when your server checks if mail recipient exist in your environment.
At that moment, all possible DNS checks are executed prior to that. Your and sender system would already "act" if DNS checks would be unsucceful (direct lookup check, ptr reverse check,  helo domain check etc)
SPF is important, but only when you send mail. It does not affect your mail receiving.

slow recipient lookup on your system could be caused by GC performance, this is why I suggested  "check your GCs performance "

I'm sorry, but what I meant earlier was what does GC stand for?  Again, sorry for the ignorance.

GC stands for Global catalog. one or more of your domain controllers are carrying this function

I will check it and get back to you.  Thanks.

In the middle of looking into this, I notice that the checkbox "Perform reverse DNS lookup on incoming messages" is checked in the properties of my SMTP virtual server.  Is this a correct setting or does this not have anything to do with the issue?

This is correct setting. When this settings enabled, your system takes IP address of the connecting system, perform reverse lookup and add results to the message header. Assuming that your DNS servers are working fine it would not have anything to do with this issue

I have checked out a few different things.  Firdt, I looked in my DNS Event Viewer for any errors.  Here's one from 5/28/08:

Event Type:      Error
Event Source:      DNS
Event Category:      None
Event ID:      4015
Date:            5/25/2008
Time:            2:00:45 AM
User:            N/A
Computer:      PCESCORPSERVER
Description:
The DNS server has encountered a critical error from the Active Directory. Check that the Active Directory is functioning properly. The extended error debug information (which may be empty) is "". The event data contains the error.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.
Data:
0000: 51 00 00 00               Q...    

Is this connected to my original issue?  I got this error 5 times within 1 minute.  It happened a month before that just like this one.  Also, I checked the Catagorizer Queue Length in the System Monitor - all results come back as normal (all at zeros).

Is there any other items I should be checking?

well, this is quite serious error. It could cause your issue(s)
there are many reasons for this error, depending on your AD configuration and history (what domain controllers you had before, what changed etc)
You might want to check these links
https://www.experts-exchange.com/questions/21301445/DNS-error-4015.html
http://support.microsoft.com/kb/267855/EN-US/
http://www.chicagotech.net/troubleshooting/eventid4004.htm

I reviewed the links you referenced. Our configuration is only 1 DC with about 30 users so the multiple DC configuration tips would not apply to us.  The DNS Server service is running just fine - as of now.  All users are able to access domain and domain features.  No one has reported any connectivity issues with our network.

Our server is configured to auto reboot after updates have been installed overnight.  Is it possible that these errors are just from the DNS Server service starting before the AD is loaded during the reboot process?  The errors are reporting during the overnight hours.

ok - here's another Event ID log message.  This is not an error - just an informational log.

Event Type:      Information
Event Source:      DNS
Event Category:      None
Event ID:      5504
Date:            6/9/2008
Time:            12:08:53 PM
User:            N/A
Computer:      PCESCORPSERVER
Description:
The DNS server encountered an invalid domain name in a packet from 204.2.178.133. The packet will be rejected. The event data contains the DNS packet.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.
Data:
0000: db 37 84 00 01 00 08 00   Û7„.....
0008: 00 00 00 00 0f 63 61 63   .....cac
0010: 68 65 30 31 2d 6d 75 73   he01-mus
0018: 69 63 30 32 0a 6d 79 73   ic02.mys
0020: 70 61 63 65 67 65 6f 06   pacegeo.
0028: 61 6b 61 64 6e 73 03 6e   akadns.n
0030: 65 74 00 00 1c 00 01 c0   et.....À
0038: 0c 00 05 00 01 00 00 01   ........
0040: 2c 00 1a 0f 63 61 63 68   ,...cach
0048: 65 30 31 2d 6d 75 73 69   e01-musi
0050: 63 30 32 07 6d 79 73 70   c02.mysp
0058: 61 63 65 c0 27 c0 43 00   aceÀ'ÀC.
0060: 01 00 01 00 00 00 1e 00   ........
0068: 04 d8 b2 2c 0d c0 43 00   .ز,.ÀC.
0070: 01 00 01 00 00 00 1e 00   ........
0078: 04 d8 b2 2e 0b c0 43 00   .ز..ÀC.


Perhaps this is referring to the emails these companies are sending us but we never get, ultimately resulting in a timed-out NDR for the sender?

this is not a problem, and it is not refering to your emails issues
there are several posible causes for this issue. Most likely it could be because of NDR's that your server is trying to send back to the spammer (and spammer address was spoofed)

Back to your comment "The delay seems to happened when your server checks if mail recipient exist in your environment.
At that moment, all possible DNS checks are executed prior to that. Your and sender system would already "act" if DNS checks would be unsucceful (direct lookup check, ptr reverse check,  helo domain check etc)
SPF is important, but only when you send mail. It does not affect your mail receiving.

slow recipient lookup on your system could be caused by GC performance, this is why I suggested  "check your GCs performance ", would the sender receive a timed-out NDR for their message after it has cleared the DNS checks?  I would think that once the their server gets a DNS "all clear" so to speak or the DNS resolves, they wouldn't receive NDRs for issues on our server.  Unless the 2 server's handshake is not initiating.  

Am I just completely wrong?

Thank you for the in-depth explanation.  Yes, we have Symantic Antivirus 10.2 Corp. installed.

Then, is there a fix to this, like speeding our server response up or is the sender's time-out response set too high?

Will check.  Thanks so much for your help.  Here's some points.

Our Symantec Antivirus version does not have SMS included.  Is there something else within Symantec that could be causing this?

what recipient filters do you have enabled?

None.  There is a checkbox that is ticked - Filter recipients who are not in the Directory.  Is this correct?

any allow or deny lists?

also, check in registry HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SMTPSVC\Parameters if you have TarpitTime listed there

Nothing under Allow or Deny lists.  Do have the registry entry set at 5, which I'm assuming is default.

I believe default is no entry, which assumes value 0. Somebody has enabled tar pitting, setting 5 seconds delay for "RCPT TO" SMTP communications
Reduce the number - set it to 1 or 2. It should fix your issue

Filter is enabled on my SMTP virtual server - both recipient and sender.  Is that the way it's supposed to be?

this is the way you (or somebody else) wanted to.  i would say it is OK

Thanks a bunch for your help.  You are AWESOME!!!!