Strange threading error

I have an application that has a BizTalk server fire xml messages into a C# Web Service. Every now and again, one of the messages throws an error. I created a console application to mimic what BizTalk was doing and was able to reproduce the error by creating a bunch of threads and firing the messages into the web service while it was processing the previous ones.

The issue that's arising is that every now and again, one of the messages is processing twice for some reason and that screws up our validation. For instance, if I have a batch of 20 messages, I can run through them four times without any issue and then the fifth time through, there are 21 messages getting processed, one of which is a duplicate of another message. We were able to replicate this by firing them through BizTalk and we got the same results.

I'm assuming that this is some kind of memory leak that causes one of the threads to fire twice because the processor doesn't realize that it's already fired. Has anyone come across a situation similar to this before and, if so, knows how to handle it?