Most of the larger countries have single letter country codes (eg, UK - G, France - F, Germany - D, China - B ), followed by four letters. That gives 456976 combinations per (single letter coded) country.
The countries that have two letter codes (eg, Australia - VH, Ireland - EI) followed by three letters, which gives 17576 combinations per two letter coded country.
Bring in the countries like the US and Japan which have combinations of letters and numbers and the number of combinations gets even bigger. The US is N and one to five numbers, one to four numbers followed by one letter or one to three numbers followed by two letters, allowing just over a million combinations (assuming my maths is correct). And that is just for the US N-register.
Japan is JA- followed by either four numbers, three numbers followed by a letter or two numbers followed by two letters, giving about 100,000 combinations.
If we assume that new aircraft can take the registrations of scrapped aircraft (and even if we don't assume that), then I really don't think there'll be a problem with running out.
However, the game itself can't be relied upon when it comes to this. There may be thousands of combinations but, we are likely to get these scenarios:
Someone intends to have 10 737s. He orders 5 first and reserves 9M-MKA-MKE, but intends to have up to 9M-MKJ. His competitor can quickly take MKF and so on just to mess things up.
I also have a feeling many won't get their desired registrations and will complain about unfairness etc