This is a variant of the "birthday problem." There are many mathematical discussions of the problem, but the basic idea and equations can be found at http://en.wikipedia.org/wiki/Birthday_attack. For 25,000 records and the 32-bit address space that you ran into trouble with, it's around seven percent. With a 48-bit address space, the probability that you will find one collision is tap - tap - tap about one in nine hundred thousand. That might still be cutting it a little close, if your data set grows over time.

Update: Sorry, I missed the question about fifty million records. With a 48-bit address space, that gives almost a 99% probability of at least one collision(!) The table in the article shows that 64 bits (sixteen hex digits) gives a one in a million chance of a collision for about sixty one million records.