Would you guys consider it a meme?
I know that it relatively started on Nico Nico Douga on June 2007. I say “relatively” because the earliest example of the meme I found on the web was a Youtube vid uploaded on April 13, 2007 by sonomamario.
The vids that followed it uploaded on Youtube were taken from (or is it “originated on”?) Nico Nico Douga, starting on June 28, 2007.
The most popular vid, of course, is the Kumikyoku vid, with over a million and a half views.
But, this vid is not the first vid to have music as its primary focus for when Mario hits a certain object. The first vid was either the Jap or the English version of the AutoMario using the song Hare Hare Yukai from the anime, Haruhi Suzumiya (though not as astoundingly as the Kumikyoku version) on September 13, 2007.