How about splitting them into groups based on first character ? If you have 26*2+10 possible first chars just generate 600/52 million for each initial letter and write them out before moving onto the next letter. I guess randomness is important here as you are not just generating the sequence 1...600M so when you hand them out first randomly select which block to get one from, them select a random one from that block (and mark it as used).

Cheers.