Well, if it comes to Mothula, I usually get the Golden Sword before beating that dungeon (you don't need the fire rod in level 5 to defeat ice enemies or unfreeze the boss, the Bombos medallion does the job just as well) because even after beating the game >20 times, I have still a hard time against Mothula, especially because you have to hit her very akwardly, the sprite and the vulnerable area actually don't match very well. I don't know exactly how many hits it takes to defeat her, but obviously the Fire Rod is more effective than the Master sword. But the Tempered Sword and especially the Golden Sword are much better.
But back to topic: I like bosses with multiple ways to defeat them much more, and that's just one of the many resons why LttP and MM are my favourite Zelda games. I think it's kind of boring and predictable to simply use the respective dungeon item (and only that) to defeat a boss and it takes away a lot of challenge. The Oracle games are an exception to that, finding the weak spot of a boss wasn't always that easy even though the dungeon item was used most of the time.
IIRC the battle against Majora could be fought in more different ways than any other (final) boss battle in the series (#2 would be Beast Ganon in OoT): Depending on how difficult you wanted the battle to be, you could use either of the five(!) forms of Link, with Fierce Deity being the easiest and Deku being the hardest. As normal Link, you could use normal arrows, light arrows, no arrows at all (depending on the phase of the battle) and you could use the Kokiri Sword, Gilded Sword or even the Great Fairy Sword. Doing a spin attack is harder with the GFS (and also swinging the sword normally is harder with the GFS), but therefore it deals more damage. Heck, you could even use bomb(chu)s for some extra challenge. Maybe there are even more possibilities to that battle! Such things greatly increase the replay values of the game, so I'm all the way for bosses that can be killed in multiple ways.
Off-topic again: For those of you who have played Final Fantasy IV and V: In FFIV your classes for the final battle are pre-defined and the boss is not very hard at all. In FFV you have to choose your classes and the abilities you learn throughout the game very wisely or else you'll fail epicly on the final boss. While I've beaten FFIV on the first try without any problems (yes, I'm referring to the "hardtype" version), I had to play through FFV twice because on the first playthrough I totally screwed up my classes and abilities and therefore stood no chance against Exdeath.
So the same applies to Zelda: [obvious] The replay value is much higher if there are different ways to beat the game. [/obvious] I like non-linear games much more, unless the difficulty is really over-the-top.