What version of Exchange are you running?
Can you use the mail tracker to take a look at the emails that are succeeding and compare them to the emails that are failing?
note: in Exchange 2007, you would open the Exchange Management Console -> toolbox -> Message Tracking.
If you can figure out what the difference is between two of the emails, it may help us help you determine what your cause is. :)