Kanto: Haunter, Cubone/Sandslash
Johto: Larvitar, Jigglypuff(Yes, the very same one who followed them)
Hoenn: Spoink(The one who followed them), Flygon, Mudkip
Sinnoh: The Riolu(Evolves into Lucario for aura), Hippo, and Snover he bonded with
Unova: Zorua, the Venipede he bonded with
Kalos: Vivillon