I cannot tell from your explanation what the ISP is doing to verify your servers, so this is rather generic advice.
I've never heard of an ISP that dynamically checked your server to see if it is an open relay. Many ISPs and business do check lists of known open relays and compromised systems to and drop email from those hosts or addresses. Your customer should verify that they aren't on one of those RBLs. They will also do queries to verify that email is coming from a legitmate mail exchanger (MX) for your domain, or to see if the IP address of the sending host belongs to a machine in your domain, etc. Some companies (like mine) utilize greylisting, which is described at
There are many many ways that ISPs and companies filter spam.
In a multi-server Exchange environment you should always utilize the concept of an SMTP gateway. The SMTP gateway is simply an Exchange server that receives all inbound messages and processes all outbound messages. The purpose of this is:
1. It frees up the rest of your Exchange servers to handle internal messages, serving mailboxes, etc.
2. It gives you a single choke-point to scan messages for viruses, spam, etc.
3. The same machine always sends the outbound email messages from the same IP address.
If you have a larger installation you should configure a second SMTP gateway server for redundancy/workload. For the sake of reference, I used to work for a large international company that had approximately 50,000 users and 175 Exchange servers scattered throughout the world, but only 4 SMTP gateway servers to handle all of the inbound/outbound messages. This was more than sufficient to handle the workload.
To make an SMTP gateway, go into each routing group defined in your organization (this is in Exchange System Manager) and define an SMTP connector. Make the Local Bridgehead the server that you want to be the gateway. Afterwards, all SMTP traffic will be routed to that server for delivery.
Things to watch for:
1. The SMTP gateway server (or servers) should all be listed in your Internet DNS with MX records. This is because some ISPs will do an MX query to verify that it is receiving email from a legitimate mail exchanger for your domain. Also, if they're not listed as an MX record then you'll never get inbound mail through them.
2. The SMTP gateway server should be in your DMZ and not hidden behind NAT/port forwarding. It should have a legitimate public IP address that it uses for sending and receiving email, otherwise receiving systems may mistake it for a rogue machine/mail relay.
The best way to really become familiar with all of this is to try implementing some anti-spam systems yourself so that you see how they work. Once you see the various options for filtering you can start proactively looking at your installations to make sure that they would pass all of the potential tests. A really good anti-spam program is called XWall, you can get it from
I've used their product at several jobs, and I have never seen a product that offerred so many ways to filter email. It's very inexpensive compared to most other solutions, and is free to try for 30 days. It also has a nice option for dealing with NATed addresses, whereby you can specify the name/address to be used by the machine that is sending the email.
