Since you asked, the odds are quite a bit better than winning the lottery. This is an example of the Birthday problem: how many people do you need to get together in a room for a 50% chance that two of them share a birthday? (23 people)

In your case, the number of days in a year corresponds to how many possible combinations of letters and numbers there are in a record locator and the number of people in the room corresponds to how much you travel (well, how many PNRs you have).

The exact odds depend on how randomly the record locators are distributed and how many possibilities there really are, but assuming that there are 36⁶ = 2.18 billion possible record locators, the odds that two of them are the same seem to be:

1 in 100000 after 209 record locators
1 in 10000 after 660 record locators
1 in 1000 after 2088 record locators
1 in 100 after 6615 record locators
1 in 10 after 21418 record locators