What is the fewest cycles to clear Majora's Mask, without exploiting glitches?
Using the guide you linked to, it looks like the amount of time you need to the mandatory parts of the game is as follows. Note that this is all with time slowed by the Song of Inverted Time.
- Get Song of Soaring: 1.5h
- Go through the swamp and enter Woodfall Temple: 4.0h
- Get Hero's Bow: 3.0h
- Get Bomb Bag, go to Goron Village: 2.0h
- Enter Snowhead Temple: 3.0h
- Get Fire Arrows: 3.0h
That's about 16.5h, or 10:30pm D1. At this point, you can now go to Medigoron and unlock Power Kegs by doing the test (as it requires either Fire Arrows or beating Goht), but it's too late to get Epona, which has to be done before 6:00pm D1. Without Epona, you can't get to Great Bay or Ikana. So basically, in the first cycle (not counting the first one when you're trapped as a Deku), you can't do any better than completing Woodfall and Snowhead.
Looking at the guide again, it takes an entire cycle to complete the second half of all the dungeons: day 1 for Woodfall and Snowhead, day 2 for Great Bay, and day 3 for Stone Tower. Since you had two days to complete all of Woodfall and Snowhead in the previous cycle, we can cross those off, and say that "cycle X" will involve completing the entirety of both Great Bay and Stone Tower. It then takes basically no time at all to enter the Clock Tower and go to the final boss.
Now the question is, can you open the path to both the last two temples in "cycle X"? If X is 3, you lose an hour or two to get Epona. The guide is less helpful here because it doesn't really measure the time needed to get the last two temple songs, but my instinct is "no". It just takes too long to collect the Zora Eggs and collect what's needed for the Gibdo well.
So, I'll say that, if you do count the first one, you need four cycles to finish the game.
This is the glitchless speedrun, which appears to use 2 cycles (counting the prologue cycle):
Less cycles should not be possible since you have to get the Ocarina on the first.
The first cycle (to get the ocarina) is completely necessary.
Using the song of inverted time, I've been able to get Temples 1-2 in a single cycle, Great bay as well as the Elegy of Emptiness in another. Stone tower temple still took most of the last cycle, though.
The downside of this is you only have 7 hearts for the final battle (3 to start, and one from each boss)
I died to majora's wrath during the final battle, triggering a GO, and the start of a new day, which means my best run ever clocks in at 5 cycles.
- Getting the Ocarina
- Woodfall & Snowhead
- Pirates Fortress/Great Bay & Ikana Valley/Castle
- Stone Tower Temple + First attack on Majora
- Majora take 2.
Assuming you can manage to not die to Majora with only 7 hearts an no faries (no time to go get them) , you could pull it off in 4 cycles.
The things that you do when the save flash has gone bad...
Without any glitches, I beat the game at least once every few years with 100% completion, meaning all stray fairies, all heart pieces, all masks including the Fierce Deity's Mask and having completed all other "missable" events like reading Lulu's journal within six cycles, not including the "Prologue" and the second round with Majora, just to be sure I keep all my masks. This is possible in both the N64 version and the 3DS version, but the speeding up of time with the ISoT in effect makes reliance on the saving functionality in the 3DS version optional, although I won't truly count myself a master until I can do it without needing to soft reset even once. As for beating the game in one cycle, regrettably, it's no longer possible. Even if you manage to take a perfect route, avoid every enemy, leave the Woodfall Temple until a later time and never pause for even a second (and yes, I grinded until I got to that point), you still can't get the Fire Arrow before 8 pm on the First Night, which is the cut-off for being able to get Epona. The biggest problem as I see it is having to traverse the Mysterious Woods twice and then having to wait forever and a day for the boat tour to reach the Deku Palace, although the floating platforms in the Inner Garden, the sluggish speed of the Deku's flight, the omnipresence of those annoying Dragonfly monsters and a few other little gimmicks slow you down just a little too much, even for someone talented enough to defeat the Dinolfos mini-boss in six seconds.