It seems if he's planning to make 100 million records with a probability of 1 in 1 million of a collision, he's going to end up with ~100 collisions. I think I would plan to make the collision probability of N records at least < 1/N. Plus, one million records is really not so big.
I do like the point that UUIDs are generally stored as strings whereas they represent a 122 bit value. Seems encoding the UUIDs as binary would offer much greater efficiency in storage space as well as indexes.
Also, to whoever downvoted my very first post here: Way to build a community @sshole. I'm never commenting here again thanks to you, jack@ss.