Those characters popped up in a time when Nintendo brought the industry out of the grave. Those three characters' initial series came out in that window between 1985 and 1987 when the industry recovered, you also have Donkey Kong who slipped in with Mario before the crash happened. So there's a bit of mystique with them being saviors for that period.
You also have Nintendo's Seal of Approval which they didn't throw around all willy nilly and which all three of those (four if we're counting DK) got on their titles. Non-Nintendo titles like Mega Man and Castlevania also got that seal and have the same longevity although Castlevania had to change the cast up and develop an actual chronology--as did Mega Man. Adding a bit more to their magic.
Finally, like Sega's Sonic those three games can cater to all ages. Even though Mario is marketed for family and kids, there's some deceptively difficult platforming and puzzle solving in those games that cater to all skill levels. Metroid is runs the scale of being able to be a Saturday morning to series to having a really bleak storyline. It's all in the story delivery with Metroid. Then you have Link which could also have that same range as Metroid, but is often kept as whimsical high fantasy. If you sat, you could easily make Legend of Zelda a consistently bleak series if you kept throwing Majora's Mask in the mix.
In short, those three Nintendo series are just flexible enough to stand time and leave themselves open to game changing mechanics and studio designs (if Retro got their hands on Mario or LoZ, oh god). I've always said Sony could've done the same with Crash and Tomba if they kept them being consistent by now. Nintendo has series that you could put on TV for kids, teens, or write for a more mature audience if they needed/wanted to and advertise during their cartoons and will impressive magazine reviewers.
Tomba and Crash (especially Crash who had Sonic attitude) could've at Saturday morning cartoons, been promoted to kids heavily, had the funky, awesome platforming of Tomba, and had that all audience appeal of Mario, Zelda, and Metroid. Hell, Tomba could've been the actual mascot for PS if they just pulled the trigger on it.
Sorry for the long explanation.