As Desperado correctly pointed out, internet email traffic occurs on port 25. If the sender is blocking port 25 on on their firewall, then their firewall (not SpamFilter) will block all outgoing connections out to the internet. To confirm this, you saw that there are indeed no connection attempts in SpamFilter from their remote IP. This is again because their own firewall is preventing SMTP traffic to leave their network.

In order to send outgoing emails, their administrators will need to allow outgoing connections on port 25. They can still leave incoming connections blocked, but the outgoing ones must be allowed.

The server in question sends mail to other servers just fine.  According to them, the ONLY server they have trouble sending to is ours.  I didn't think we would need to contact their server to receive from them, but I thought I'd ask

It's possible the administrator(s) of the sender's domain are not troubleshooting this correctly.

SpamFilter accepts incoming SMTP traffic on TCP port 25, which is the RFC requirement to process internet emails. When a remote server establishes a TCP connection to port 25 on SpamFilter, the "return" TCP traffic from SpamFilter to the remote server will occur on a random TCP port established by the remote server (this can be any port except port 25).

SpamFilter will never attempt to contact back the remote server when processing incoming emails. If the remote administrators are stating that unblocking  "inbound" port 25 on their firewall solves the problem, I would have to doubt the accuracy of that statement, as there is absolutely no traffic from SpamFilter to the remote port 25.

I checked the domain name for the email address you used to signup on this forum. If this is the domain to which these failed email attempts are being sent, we can see you have 3 MX records for the domain, and on each one of them you have SpamFilter running. You are running v4.1.2.812 on the first 2 MX records, and v4.0.1.786 on the 3rd MX record. The version mismatch on one server has absolutely no impact.

I do see however that you have enabled greylisting on all 3 servers. While this will cause an initial delay of possibly a few hours for the very first email to be received from a remote server, after that first email is received there will never be any problems in the future. In addition, even with greylisting enabled you will see the IP address of the remote server's connection attempt being logged in SpamFilter's activity logfile.

When you said 

gillonba wrote: We cannot find any connection attempts from their IP in our Spam Filter logs

, have you checked for the presence of the IP in the logs for all 3 of your SpamFilter servers? If you did, and the IP was not logged, you can be certain that SpamFilter did not receive a connection from the remote server. If your servers are behind a firewall however, you should also check your firewall logs to ensure that it was not your firewall that blocked the connection attempt. However I must always go back to the remote admin's statement about unblocking port 25 and this solving the issue, as this is again a very "strange" statement...