In the last couple of days, I have received complaints from customers not able to receive email from certain sites.
If I understand you correctly, you are saying that these sites are not able to send mail to you. Assuming that they are diverse sites that don't have significant similarities, this suggests that the problem is on your end.
From these sites, I can't connect to our mail server, on other sites, I can.
I don't understand what this is supposed to mean. It's their mail servers that are supposed to try to connect to your mail server.
We have tried sending email, and we have also tried telnet on port 25 to the server. I can't seem to find a correlation. There is no firewall on our network. We have an access list to filter port 25, but this server is allowed. Our mail server is also our DNS server. From the sites that I can't connect to our server on port 25, I can query the DNS server using nslookup and get a response.
This doesn't tell you anything about why their mailservers might not be able to reach your mailserver.
I tried tcptraceroute from one of the sites where I have a unix account, but it is behind a firewall, and it dies after the first hop. I'm stumped. Any suggestions.
You really haven't given a clear description of the problem. When you say customers can't receive email from certain sites, I'm assuming this means people at those sites send email to your customers and the email does not appear in your customers inboxes. From this, I would conclude that their mailservers are not able to (or willing to) send the email to your mailserver. When you say you can't connect to your server on port 25, where exactly are you trying from? Did you try emailing (or calling) the administrators of those sites? If you use SPF, are your records valid? Do the senders get any bounces? Your statement of the problem is lack of specifics. We can't check your SPF records. We can't check if those domains have a common provider. So all we can do is tell you to troubleshoot. DS