Bessie Bass from Yoshi's Island DS, she can just take forever to go and you only have to hit her three times and if you take too long your baby will get kidnapped and taken to Bowser's Castle and have to start again.
Waiu from Kirby's Dream Land 2. And often Efreeti from the same game. Heck, every Mid-Boss in that game is hard, really; they even managed to make Mr. Frosty difficult (well, somewhat more so than usual, at least).