Hal,
I'm going to put a very heavy IMTU disclaimer on this, because I'm a huge heretic on the subject of citizenship, sophonts' rights, and the distinctions between Imperial and planetary law in Traveller.
Just as the starport has its extraterritoriality rules, what rules apply to that of the fief? Is it considered to be Imperial held lands subject to the laws of the Capital as if it were Imperial soil, or is it subject to the laws of the planet itself?
There are many possible circumstances here that might make things unique. For example, in some cases the fief may be located inside the starport's extraterritoriality line, which would make it except from local law. Alternatively, the noble could have a function in the world's government (or might even be the world government), in which case their fief may have special status. But as a broad generalization, and assuming that no special cases apply, IMTU a noble's fief that is located on a world is subject whatever laws that world's government might make - it is merely a plot of real estate. However, local laws that are not aligned with Imperial law are unenforceable against Imperial Nobility (which includes anyone holding a knighthood or above and their immediate family), or authorized representatives of a high (typically baron or above) Imperial Noble who are conducting Imperial business. Just like the starport's extraterritoriality, this concession to the Imperium is a condition of and codified in the world's treaty of admission to the Imperium.
So, for example, the religious dictatorship of Arglebargle X may pass a law that requires residents to publicly swear allegiance to the Grand High Poobah upon first leaving their abode each morning, on pain of public execution by the Poobah's Morality Police. Individuals residing on an Imperial Noble's fief on Arglebargle X must obey this law. However, Arglebargle X may not enforce this law (or any other laws that are not also Imperial law) against the Duchess of Foobar when she is visiting. Should they try to put the duchess to death, the Emperor (and his representatives, the Nobility) may take whatever steps they feel are necessary to prevent or right this wrong. SO Morality Police that attempt to arrest the duchess may find themselves staring down the barrels of the "ceremonial" fusion rifles carried by the duchess's honor guard. Note that the "authorized representatives who are conducting Imperial business" allows the duchess's honor guard to effectively bypass local law level.
Also IMTU, local laws that are not aligned with Imperial law may or may not be enforceable against Imperial Citizens. Imperial Citizens are individuals that have been granted that right by the Emperor or his representative, usually in recognition of years of loyal service (typically honorably-discharged Navy, Marine, or Scout veterans). Imperial Citizens who are convicted under local law may appeal to the Imperial Consul, who may (or may not) choose to intervene. SO, an ex-Navy veteran who is an Imperial Citizen might also be arrested by the Morality Police for failing to swear allegiance. While he or she can appeal to the Imperial Consul, in practice, the Imperial Citizen might well be executed before the Consul acts. The veteran's best bet may be to evade arrest (or stage a jailbreak) followed by a sprint to the starport's extraterritoriality line.
If people are citizens/subjects of the world they are born upon, what is the status of someone who is born within the confines of a Baron's fief? Is the person who is born within the Baron's fief, truly an "Imperial citizen", or is he a subject/citizen of the world he is born upon?
IMTU, people who are born within the confines of a Baron's fief are subjects of the world, just like anyone born anywhere else on the world, UNLESS they happen to be the child of the Baron or someone else who holds a patent of nobility from the Iridium Throne (members of the immediate family of an Imperial Noble are considered Imperial Nobility). Imperial Citizenship is separate from nobility, and typically must be earned through service to the Emperor.
What is the status of someone who is born of a parent who is a subject/citizen of one world, and whose other parent is a citizen/subject of another?
IMTU, everyone who isn't Imperial Nobility or an Imperial Citizen is the de-facto subject of whatever world that they happen to be standing on. These individuals may have claims to citizenship on different worlds, but this claim is useless unless the world that they are standing on recognizes that claim to citizenship and grants specific rights based on it.
So in your specific instance, a child born to two individuals who are citizens of two different worlds (and neither of whom are Imperial Nobles), may be a citizen of either of the two worlds, both worlds, or none at all. Regardless, that child will be subject to the laws of the world that they are born on, until they leave.
All of this talk about who holds what fief and whether a fief can be lost or what have you... What isthe basis for this? Are "titles" transferable or inheritable within the Imperium? If not, then what is the point of being an honor noble versus a standard noble if the ownership of any given fief is transitory? More importantly? Why is there a nobility track if parents can lose a particular fief?
IMTU, there are two distinct types of nobility - "honor patents" and "precarious tenure". Knighthoods are different, but behave basically the same way that honor patents do.
Knighthoods and honor patents are granted by the Emperor or his representative in recognition for exemplary service to the Imperium. Knighthoods are typically associated with a specific act (foiling a Zhodani plot), while honor patents are typically associated with a specific office which must be held be a noble (such as Ambassador or Sector Admiral). If someone who does not already hold a suitable title is appointed to the office, they will also receive an honor patent. Knighthoods and honor patents expire when the recipient dies - they cannot be inherited. They typically do not include a fief, but usually do include a stipend, which is paid directly from the Imperial treasury. The immediate family of an honor noble are considered Imperial Nobility while the noble is alive. In theory they lose that right when the noble dies, but in practice recipients of honor patents will use their power as representatives of the Emperor to grant Imperial Citizenship to their immediate family members (but exceptions do exist, such as when the noble disowns a "black sheep" child).
"Regular" nobles receive patents of nobility with precarious tenure. These patents typically include a fief. The title and fief are inherited from one generation to the next, but can be revoked by the Emperor at any time. In practice this type of revocation is exceedingly rare, and is usually only done for nobles that are in rebellion against the Iridium Throne or who become notorious criminals. Instead, the noble's chosen successor must be confirmed as heir before he or she can inherit. This provides incentive for noble parents and prospective heirs to behave reasonably well (or at least, not egregiously badly) and to give their heir the type of upbringing and education that a noble should have, so that the title will be confirmed when it is passed to the next generation.