I'm thinking that you could get a race condition only if the same cookie came in at the same time (with, say, a different query string). I'm not sure how likely that would be and anyway a lot rarer than the OP is experiencing.
I'd be intrested to find out if I'm wrong. I'd have a lot of code to rewrite. :-)