Great article, Justin. You mentioned some characters I'd never even heard of before, so it was informative as well as fun.
Just to throw out characters that would be great to see but have no chance of showing up:
Captain Rainbow,
Wart from Super Mario Bros. 2,
one of the cars from Stunt Race FX,
the three boys from Marvelous: Another Treasure Island (they could be used a s a team like Pokemon Trainer of Ice Climbers),
the Gerudo Warrior from Ocarina of Time,
Chibi Robo,
Pokemon TCG player (the damage you deal will depend on what Pokemon card you throw!),
Starfy,
Stanley from Donkey Kong 3.