For instance, Clovis I divided his realm among his four sons, who all became independent. Charles Martell divided his realm among his two sons. The realm of Louis the Pious was also divided into three parts in the Treaty of Prüm/Verdun, one of which would become the kingdom of France.
Now my question: If a vassal of one of these kings had holdings in, say, East Francia and Lotharingia, would he give up part of his holdings (if yes, would he be compensated in any way?), or would he owe fealty to multiple kings?
Were there different solutions between peaceful inheritances (Like after Charles Martell's death) and less peaceful divisions (like the Treaty of Prüm)?
I can't speak for early Francia, but the concept of in effect being multiple separate people at once was fairly common. For example, Richard Coer de Lion, ruling his father's Angevin Empire, was both the king of England in his own right, but also the vassal of the King of France as the Duke of Normandy, Aquitaine, and Bretagne. Does this mean that England was part of France? No. Richard King of England and Richard Duke of Normandy, for legal purposes, are different people. This also happens the other way round. James VI of Scotland and James I of England for example were in reality the same person, but until the Acts of Union in 1707, The Crown of Scotland was separate and completely unrelated to the Crown of England, except in the respect that they happened to be worn by the same person at the time.
One of the more Humorous (in my opinion) anectdotes of the Norman period was when William the conqueror Rufus was warned of his half brother uncle, the bishop of Bayeaux.
A: "He is plottign against you sire, you should arrest him"
W: "Arrest him? He's the bishop of Bayeaux, I can't arrest a clergyman"
A: "My liege I am not asking you to arrest the bishop of Bayeaux, I'm asking you to arrest the Earl of Kent"
Because, as it happened, the Bishop of Bayeaux and the Earl of Kent happened to be the same person, Odo.
While accurate for the periods their describing, I'm not sure if the previous answers are of very much help when talking about early medieval kingdoms. Certainly in the Carolingian period, things didn't work in the way described in previous answers, although the end result tended to be similar.
The first thing to note is that there was no 'feudal law' or set of uniform regulations which dealt with how the aristocracy dealt with the crown. There were certainly royal vassals (usually called vassi dominici in our sources), but they weren't ubiquitous and certainly not all of the major political players or aristocrats would have had that status, which implied a special oath and connection to the king, above and beyond what was expected of other subjects, and the status seems to have implied some sort of special treatment (including, but certainly not limited to, and certainly not always, receiving lands from the royal fisc to be held in benefice, i.e. temporarily or for the vassal's lifetime only). Going beyond the case of vassals, throughout the empire there was a recognized and clear distinction between allodial land (that is, land which was owned in full by the aristocrat and his family, passed down via inheiritance) and honores, which is what the bundles of offices, lands, privileges and duties which were allocated by the kings were called (which could be taken back by the king at any time and would be redistributed on the death of the incumbent).
So, back to your question of what happened when the Empire split? As a general rule, this was not really a problem for any but the highest ranks of the aristocracy. The majority of the Carolingian aristocracy was local and this there would have been very little change for them, unless they were unlucky enough to end up on one of the newly drawn borders. For the families who made up what historians have called the Reichsaristokratie (literally, the 'Imperial Aristocracy') things were more complex. These were a group of families who mostly had their origins in the Carolingian heartland of Austrasia (roughly the area between the Rhine and the Meuse), but who were used by the Carolingians to spread Frankish rule across the Empire, holding lands and important offices in places which did not identify as ethnically Frankish in particular (such as Italy, Bavaria, Septimania, etc.). When the Empire split, aristocrats help onto their allodial property in full, no matter where it was, in theory at least and in practice at least some of the time, as the will of Everard, Marquis of Friuli in the Kingdom of Italy shows. It was written in 863-4 and shows that he held lands which stretched from Italy up through the Alps in modern Switzerland and Swabia right up to modern Belgium. But this example also helps us see the practical consequences of what imperial divisions did to aristocratic families: they began to divide their own assets up geographically, with one son given the property in one kingdom, the other all the lands in the other kingdom. This is visible to a certain extent in Everard's will, and more explicit in other sources. It seems to be a fairly consistent pattern for aristocrats from the mid 9th century.
As for the honores, the bundle of offices and property granted out at the discretion of the king, you would lose them if you sided with the wrong brother/cousin, of obviously why would the new king reward someone who fought for a rival? So if you were, say, the Count of Orléans, but chose to fight for Lothar instead of Charles in 840, then you could expect to lose your county, although you might well be given new honores in Lotharingia as reward for you service. For this reason we often find aristocratic families often taking regional political strategies to protect their assets: one son/cousin fighting for each claimant, making sure that whatever the final division, all of the property would stay in the family.
Good accessible sources for this sort of stuff:
Chris Wickham's chapter on the 'Carolingian Century' in The Inheritance of Rome (London, 2008), esp. pp. 401-4, where he discusses Everard's will.
MacLean, Innes and Costambeys, The Carolingian World (Cambridge, 2005) is a great introduction to the period as a whole, and has a separate chapter on the aristocracy and its relationship to the Kings.
Stuart Airlie's chapter on the Carolingian Aristocracy in the NCMH, vol 2. Airlie is my go-to source on anything in-depth on the Carolingian aristocracy, so follow the footnotes here for anything in-depth you need.
To build on what /u/Ulkhak47 said: it was also completely possible to be a de jure subject of multiple different sovereigns. Frederick I of Prussia was simultaneously the subject of the Holy Roman Emperor (as Frederick III of Brandenburg) and the subject of the King of Poland-Lithuania. The King of Poland-Lithuania was Augustus II the Strong, who also happened to be Elector of Saxony (as Frederick Augustus I). Therefore, according to convoluted feudal law, Frederick I was simultaneously the subject of his peer in Saxony and, separately, the subject of the Holy Roman Emperor (who, in turn, was the suzerain of Augustus in his capacity as Elector of Saxony but not in his capacity as King of Poland-Lithuania).
This all got even weirder when Frederick became King in Prussia, using the legal fiction that he was only a king when he was within the de jure borders of East Prussia. Augustus consented to this, so the King of Poland-Lithuania (in his new capacity as King of Prussia) became the suzerain of the King in Prussia. This also conveniently allowed Frederick to avoid running afoul of the old Imperial laws that said only Bohemia could be ruled by a king (because Brandenburg itself wasn't ruled by a king -- it was ruled by an Elector, who also happened to be a king outside of the empire).
Feudal law is wonderfully bizarre.