In discussion with he told me that he figured out that current way of generating long ids for trace is increasing probability of repeating the same number 8 times (as we do 8 times 8 bytes generation). As internal state of Random is 48 bits this means that actually we are on 45 bits (48 - log8). as we can expect collision on half of the bits, we are somewhere in region of 2^22-23.
In normal words after 5931641 generated id we would have probability of 50% for collision.
Commons math3 offers implementation of the Mersenne Twister algorithm (This generator features an extremely long period (2^19937-1) and 623-dimensional equidistribution up to 32 bits accuracy.) We can use two generations of 32bit ints to get a real 64bit spread long. And we would still be fine.
It's not thread safe so it must be in a thread local. Apache Commons Math3 works with Java5. Only problem is dependency to the sdk project. We can alternately just copy part of the algorithm that we need