Only three minutes into the first video and wow. Nice find, can't believe I'm just hearing about this now.
All together now, "Club Nintendo Reward."
Edit:
I took the liberty of adding series titles to Kenology's links.
Who'd have thought "Dark Overworld" from Zelda: A Link to the Past would sound so good as a jazz arrangement. Plus the Skyward Sword theme for extra greatness. And as someone who has no interest in Pokemon music, that guitar and New Orleans jazz intro (with some cool funk to follow) sure is close to changing my mind. It may be the most fun arrangement of the bunch.
The arrangements are credited to Masanori Sasaji (笹路 正徳), whose VGMdb credits are a bit slim but has produced some of the bigger (and more respectable IMO) J-pop acts.
http://vgmdb.net/artist/5125