Queries :: Adding New Records To Table - Random Number No Duplicates

I have a form which allows the user to add new records to a table. After the user had entered all the information into the form, they click a command button to add the record. In addition to adding the new record, my command button runs an query which is supposed to generate a random number between 1 & 1,000,000,000 and update the record ID field with that number.

Here is the formula I have been using in the "update To" now of my query: Int((1000000000-1+1)*Rnd()+1)

My problem is that I keep getting duplicates. You would think that the chances of getting a duplicate number would be pretty small with this large of a range, but I get a duplicate almost every time.

I have tried indexing (No duplicates) the field in the table, but that did not work. When my query generated a duplicate number, the record was just not added to the table.

I also tried a two step approach:
1-Make a table of all in use record ID numbers from my table (tblIdNo)
2-Update new record with a random number that is not in tblIdNo

This was a no-go too

How to build an update query that will update each new record added to the table with a random number between 1 & 1,000,000,000 without any duplicates? This seems like it should be so simple, and I am starting to get really frustrated.

I would prefer to accomplish this through a query/queries (if possible) rather than with 100 lines of code. This database is not for me, it's for another group, and the individuals in this group are totally freaked out by code.