Exchange not delivering e-mails

For approx 1 month now we seem to be having a problem with Exchange2000 in that some messages are being recieved from our ISP and are not being delivered to the reciepient. When I check in Message Tracker I can see the message being recieved by get only the following information –

SMTP: Store Driver: Message Submitted from Store
SMTP: Message Submitted to Advanced Queuing

This is only happening to certain messages and to certain clients. This appears to be happening to randon messages as other messages from the same sender are getting to the same receipient.

Anyone any ideas?