It appears that NMinimize uses BlockRandom with a fixed seed, so any stochastic function passed to NMinimize will always produce exactly the same result. I can work around this, just observing how NMinimize works. Example:
In[20]:= f[x_?NumericQ] := (Sow@RandomReal[]; x^2)
In[21]:= Last@Reap@NMinimize[f[x], x] == Last@Reap@NMinimize[f[x], x]
Out[21]= True
