How did the king give land to new barons without taking it from the old ones?

I cannot offer a complete answer but some relevant facts, many from my history degree or from having subsequently studied law. In theory, no one absolutely owned land but the king, everyone else if they had land 'held' it of the king. Hence the most complete from of land ownership that someone can have even today is 'freehold' i.e. held as a vassal of the monarch but 'free' of having to pay rent or perform knightly service etc. (Source, Halsbury’s Laws of England 5th Edition, Vol 87 [2017 reissue] para. 19)

Hence in Medieval times if a Baron was e.g. executed for treason (say, having picked the side that lost in a rebellion or civil war) his land reverted to the Crown, who might grant it to some other knight or baron as a reward for loyalty (picking the side that won in the same rebellion or civil war) - see the example at the end of Shakespeare's 'Richard II' when the new king Henry IV having successfully rebelled and made himself the new king and then put down a further rebellion orders the defeated rebels executed and awards their lands to those who remained loyal to him.

Even today in England if someone owning land dies without a will and without any relatives to inherit the land, ditto in some circumstances if a limited company that owns or leases land is dissolved, the land or lease reverts to being Crown land on the basis that it always was the monarch's to begin with. This is called 'bona vacantia'. There is an obscure 'Bona Vacantia Division' of a government department in Croydon to administer this. [Before I am told off by the vigilant 'you must quote your sources' police on this website anyone can easily verify this by Googling 'bona vacantia'.]

Your example where the king gives 99 barons land and some of them sub-divide their landholding between knights: this did happen and was called 'sub-infeudation' [Google that as well, pedants! there is a Wikipedia article on it] but once the knights began sub-dividing their holdings as well it became legally and practically difficult for the nobility to extract all the rent or services due to them as is recited by Section I of the Statute of Quia Emptores of 1290. Section II of the Stature therefore banned further sub-infeudation. (Source: Quia Emptores, passed during the reign of King Edward I, one of the oldest Acts of Parliament still in force. On the UK government legislation website, helpfully in English translation as well as the original Medieval Latin: http://www.legislation.gov.uk/aep/Edw1/18/1/contents. As I have said, this Act is still in force, so you had better not go round practicing sub-infeudation!)

In most of England primogeniture applied, which meant the eldest son got all the land and any others had to seek their own fortune in the world. (Kent and some towns including Nottingham had different customary inheritance rules - See https://www.thefreedictionary.com/gavelkind or Google ‘Gavelkind’ – equal division among the children; See Wikipedia article on 'Ultimogeniture' or Google ‘Borough English Inheritance’ – basically the youngest son rather than the eldest inherits the land.)

Hence even in the eighteenth century a significant proportion of emigrants to the American colonies were the younger sons of landowners who did not inherit the land and had to make their own fortune elsewhere. This may have remained a sore point with some of them: it has been suggested (I regret I can't remember where I read this) that opposition to primogeniture in the new United States was partly because its leaders were or were descended from the younger sons who resented the fact that they did not inherit any of the family land back in England. Thomas Jefferson introduced a bill to abolish it in Virginia in 1777.

Primogeniture was not the norm in most other European countries. While it seems unfair it had advantages. If estates and farms had to be sub-divided between all surviving sons they might become too small to be economically efficient or even viable. Also, in Anglo-Saxon England a kingdom tended to be inherited as a whole: contrast among e.g. the Welsh or in early-Medieval France the kingdom might be split between surviving sons, leaving smaller kingdoms less likely to strong enough to maintain their independence and often likely to fight each other.

Your statement "I think that there are around 10000 shires in England today" - no, a 'shire' is effectively the same thing as a County, hence 'the County of Yorkshire. There are less than 50 in England. [Source - I am English, so know this]. There are a much larger number of lords of the manor, see Wikipedia https://en.wikipedia.org/wiki/Lord_of_the_manor I do not know how many, you may be thinking of that. This is mostly a feudal relic nonsense I wish was abolished, and most people are unaware of them. However, as relics of the old feudal manors they did have right to receive nominal rents from what was known as Copyhold land until the 1930s, and they can pop up unexpectedly and claim right to minerals discovered under people's land even today. This creates a legal problem over ownership of underground oil deposits that has partly inhibited the spread of 'fracking' technology to extract oil deposits in England in recent years.