And years after getting the game, I've finally beaten it on medium.
I was stuck for two years on freaking Mecha Birdo, although I rarely played the game during that time. Last tuesday I randomly beat him (her? it?) and then started playing intensively, beating the other 6 bosses and the game. Looks like I got a lot better; back then it took me months to get through the graveyard section.