QUOTE(Derek T @ Mar 23 2008, 08:18 AM)

Then it would appear that the solution is in your own hands! It's your server - set it up how you need it to work.
In agreement here. From the story as told and understood from this side of the screen, but also having to toss in an assumption or two ....
You run your own e-mail server. It would be considered rare that an e-mail server would be placed on a system with a dynamic IP Address. So my initial assumption is that this e-mail server is actually at a fixed (static) IP Address. Your definition of the delivery problems would not seem to be due to this server's output.
So this tends to take me to a similar issue related in a number of previous Topics opened up by others that deal with a user's failed attempts to get his/her outgoing e-mail to be accepted by his/her ISP/Host. The problem found in almost all of these is that the ISP/Host involved used the SpamCopDNSBL in a blocking fashion
and the user's 'connection' IP Address had made it's way onto the SpamCopDNSBL due to a compromised computer being involved, either the user's computer itself or more typically, another computer on the user's (usually) wireless network that was spewing spam.
From the details offered, I believe I'm agreeing with Derek's suggestion .. it sounds like "you" are using the SpamCopDNSBL on 'your' e-mail server in a blocking fashion. This would support your described issue of
only some of your remote customers being 'blocked' ....????
However, it would seem that this fact could be showing up in full detail in your e-mail server's logs .... though admitting that I know nothing about Kerio's software/tool-set. Wondering if the lack of detail in the rejection message (no IP Address, for instance) might also be a configuration issue on 'your' e-mail server ..????