There were probably plenty of villians faced between games that we don't really know about. As mentioned earlier in the thread, there's the monsters defeated by the Hero of Men as well as the Interlopers. And if you really think about, certain bosses such as Bongo Bongo have to have some sort of story seeing as they were sealed by somebody prior to the events of their respective games. But when it comes to villians holding Demise's malice, the only 2 we know for certain before Ganondorf are Vaati and Demise himself.