Not sure if this helps at all, but in the past I experienced a similar issue (old zen) and it actually ended up stemming from the way I had a my shipping module configured in Zen.
It was a while ago, but I recall it ha something to do with "Zones" I was using. I too thought it was the "products" in the cart, but it turned out to be a few LOCATIONS that were mis-configured on the Shipping side.
So, that may be something to look into as well. Are the customers that are having this problem all located in a certain "state" or "state's", etc..?
I was able to duplicate the problem (and figured out it was the shipping setup) by creating a NEW account in the system (like I was a customer) and used my email address, but the exact same shipping, billing, etc.. address entered by the client having problems.
This triggered the event, and I was able to then narrow down those locations within my shipping configuration (in the Admin).
Just a thought.