This is based on this Reddit question, but I rectified its mistakes.
For example, some European colonies in China were leased for 99 years, like German Kiautschou and the New Territories (but not Kowloon and Hong Kong Island).
When Germany forced Lithuania to give back the Memel territory in 1939, Lithuania got the rights to use the harbors and of free trade and way for 99 years. Why was such an uneven number used?
The origins of the 99-year lease are unknown, but have been a matter of speculation for centuries. However, that figure had become commonplace in many countries by the eighteenth and nineteenth centuries. It is thus unsurprising that negotiated territorial contracts included "99-years" as a 'default period' in many cases.
The English jurist and politician, Lord Edward Coke wrote on the subject of the duration of leases under English common law in the sixteenth-century. This can be found in the first part of his Institutes of the Laws of England in the section on the laws covering "Of tenant for yeares".
Firstly, he observes that a lease had to have a fixed term. So, for example, one could not say that a lease was granted "for as long as he shall live". Such a lease would be void under common law:
"… as if one make a lease for so many yeares as be shall live, this is voide in prasenti for the incertainty."
Similarly, one could not just say "for three generations". A lease had to specify a fixed term. He notes that in the past, leases had been granted:
"… for a hundred or a thousand yeares, &c… "
"… a lease for yeares, though it be for a thousand or more, which never are without suspicion of fraud; and they were the lesse valuable, for that at the common law they were subject unto,… "
So, in Coke's time, 1000-year leases apparently carried a suspicion of fraud under Common Law. From this was born the legal fiction of the 999-year (and 99-year) lease as being something materially different from a 1,000-year (and 100-year) lease. (Presumably under a legal argument along the lines of: "No, m'lud, this isn't one of these dodgy 1000-year leases that the law frowns upon, it's just a 999-year lease!")
It's worth remembering that leases at that time were usually much shorter (21 years is a figure often quoted by Coke), but contemporary records of leases for 99-years and 999-years are known.
It is thought that the 99-year lease was meant to represent "3 generations" and a 999-year lease was meant to be a "lease in perpetuity" without actually giving away title to the land.
This is further discussed by Stanley L. McMichael in his book Long Term Land Leaseholds: Including Ninety-Nine Year Leases:
In England during the sixteenth century it was common practice to make leases for a term of three lives or a period of 99 years. It is presumed to be upon the theory that the lease should last thru three generations as it has been common practice to accept thirty-three years as the span of a single generation.
McMichael also cites Coke:
Lord Coke, who lived in the reign of Queen Elizabeth, in his writings on the subject of leases suggested that a lease for 1,000 years might on its face suggest fraud and it is thought that to avoid such a contingency the lessors of those early days set upon 999 years as the extreme limit for the life of a lease. Such leases, in any event, were made at that time.
As the Wikipedia article on the 99-year lease notes, the 99-year lease became the maximum allowable by statute in many states in the US. It also became a de facto standard under English common law.
So, while the origins of the 99-year lease are uncertain, it was a standard under English Common Law by the sixteenth century, and commonplace in many countries by the eighteenth and nineteenth centuries. It is thus unsurprising that negotiated territorial contracts included that as the 'default period' in many cases.