Whenever you wanna find something brand-new that's being removed by record labels, just search on youtube for the song title (in this case "blossom"), and go to Search Options --> Sort by: upload date. In that way you get the very latest video's.
Took me 5 seconds to find the re-uploaded version:
http://www.youtube.com/watch?v=vnRWhnWl6g4
Avex is probably after this, though. So watch it quickly