I never have understood why everyone thought that Lucario was likely to be cut. He's practically a highlighted character in the main series Pokemon games. In Black/White 2, they place a Riolu early in the game so you can have Lucario later. In X/Y, they literally give you a Lucario as your introduction to Mega Evolution. So, I get confused when he is referred to as the "flavor of the month" considering he's been able to stick around and remains one of the most popular Pokemon (as opposed to Jigglypuff).
Also, I believe Toon Link stuck around because Nintendo decided to remake his game, so he was still fairly important. Every character is going to have a different story.