But that very factor of timing does make it easy for characters who *choose* to remain a team to do so. LEW has had a number of pairs who have formed especially cloes friendships: Telerin/Aranel, Iggy/Sara, Rurik/Sturm, just off the top of my head, have all done series of adventures together. SlagMortar has some other examples. The characters in the Monemvassia series mostly stayed together through multiple adventures -- Nurlan and Tenebrynn for all four, others for overlapping subsets.
These have generally been characters of the same level, starting out together, but not always. The M-series crew recruited two first-level characters to join them in M3 when most of the rest were 4th. There are obvious reasons why many people prefer to play with characters of the same level, but if someone is interested in playing a mentor to another PC, and someone else is interested in playing an apprentice sort, and they happen to meet at appropriate stages in their careers, there's every reason they could choose to stay together as a team.
I guess you may have seen this, but I haven't seen it on any of my adventures as a GM or a PC. Plus, this doesn't address the roleplaying issue, nor does it actually allow a good opportunity for a character who wants a sidekick (particularly if they want a certain sort of sidekick). Let's pretend that we used your idea and eliminated Leadership. Now level 9 Vanitri goes to look for an existing PC 2 levels lower to be a sidekick as per your suggestion. Unfortunately, there's an incredibly slim list of pickings, and it's likely that those PCs are already on a separate adventure and/or don't want to be a lackey. SlagMortar's idea is nice because it essentially creates a new character (or builds off an existing NPC) that is exactly the right level and exactly the right kind of cohort, which can be an issue too (let's say a Merlin PC really really only wanted a Paladin cohort, his Arthur. He's going to have a bad surprise when he looks at the level of PC Paladins).
Perfect! A built-in system for a character who starts as a sidekick of significantly lower level to gradually develop into a peer of her mentor.
But in many cases, it does so far too quickly. At level 6, it starts out sort of reasonable (+33% XP for the lowbie), but it still means that the cohort will level up to 5 in the time it takes the level 6 guy to get halfway to 7, so you don't really maintain a cohort relationship for more than half a level (which can be nothing depending on how the adventure starts--I've seen a group get half a level in a week real time when the adventure started with a fight). At high levels, it becomes even more extreme. Let's say a level 10 Merlin PC takes a level 8 PC cohort. The level 8 guy is getting
60% more XP, so he'll level in less than half the time, and then still 35% more at level 9, so he'll level up to 10 barely after the mentor hits 11, and then the cohort PC gets +36.36% XP, causing them to share part of level 11 at the same time.
Two important things to note from the example: First, this is only one level after the higher-level character grabbed the cohort that they are exactly the same level, so you barely get a cohort at all.
Second, edge effects can cause...greater concerns than this. For instance, one of my adventures just had a climactic encounter that gave 9250 XP to each 8th-level member of a group of 6s to 8s. Let's scale that up two levels by going diagonally down-right two from the closest number on the XP chart. We get 12000 for the level 10 guy and 19200 for the level 8 guy. But my numbers are slightly lower than the chart, so we'll say 10500 and 16900. This puts the cohort at level 9 (missing 100 XP) and the upper-level guy at just
barely level 11. Now if they fight something weaker, say 6111 for the level 11 guy, the level 9 guy gains 10000 XP and levels to 10 (down 100 from level 11), while the level 11 guy isn't even two thirds of the way done yet. Now, if they fight something trivial (like a CR 4), they share a level for over 1/3rd of the level.
But what if they don't? I won't bother with the extended math, but it's possible for the cohort to wind up with more XP than the mentor by level 13. Yay for weird math (or not

).