Random() instance in web farm

I'm running an application on multiple web servers that communicate with a distributed in-memory caching cluster, where I generate exclusive lock IDs on the application server -- the problem is that in high concurrency of parallel execution it is possible that more than one execution across all servers would generate the same pseudo random lock value.

The idea would be to initiate a single instance of the Random class per application pool using an incrementing seed within the distributed caching cluster, and to re-seed the randomizer after each helper method to generate a thread safe random number has reached a specific number of invocations.

Interested to see what thoughts you would have on this.