greylisting from multiple sources

We're seeing a problem with greylisting, one that our customers are 
seeing enough and getting antsy about.  While the tuple of (IP, sender, 
recipient) works fine, it has a problem in dealing with SMTP servers 
which send from multiple IP addresses the same message, or different 
messages.  Once the first message is whitelisted, successive messages 
can not be assured of arriving that quickly since they may be going out 
on a different SMTP server.

Any ideas how to deal with this?  Turning off greylisting is currently 
the largest vote, despite the flood of spam which is destined to return.

The next idea is to try to monitor and whitelist as many large IP space 
as possible.   This would cut down the very long delays we are seeing in 
email arriving.  For example, we're seeing Earthlink/Mindspring  take 
upward of 6+ hours for messages to arrive through the embargo.

tim