Peter, have you considered that it might be caching rather than a race condition? Were you remembering to flush the cache while testing?
That seems an important consideration when testing an implementation that is designed to make heavy use of caching.