MilkyTracker would work for you as it has pretty good ProTracker compatibility but that's really not the issue as the music isn't going to be played on Amiga but on cell phones. "Easiest" is subjective. A Windows GUI based tracker could be easier for some, but you get essentially the same effect by switching MilkyTracker into the MilkyTracker edit mode which makes the UI focus based and gives you modern standard clipboard shortcuts for example. It cannot import MIDI files though. Open ModPlug Tracker might help you with that. But that's all subsidiary because you are not going to produce a quality module file by converting a MIDI file. A ProTracker module is a seriously limited medium and making it sound good requires hard manual work.
The 100k is not a problem, but "incredible" is again subjective. You need to understand how a module file works. Even if MilkyTracker supported VSTi, it would only help if cell phones supported VSTi as well. You're not rendering a wave file and compressing that like with MP3. The .MOD player (in the cell phone) creates a similar environment for playing back the music as you use in a tracker when composing it. A module file stores note and effect data like a MIDI file but also contains the sound samples which act as instruments. When the module is played back, those samples are played and mixed in real-time according to what's written on the module patterns.
The durations you mention don't matter much because this isn't streaming audio. You can have a module and have it take up some kilobytes, but when you say, slow it down to quarter of the original speed, that only means changing song parameters and the file will take up equal amount of space as the original. With streamed audio the result would be quadruple.
How do I get great sounding instruments into such a tiny file?
Let's put this in proportions: The ProTracker module format is roughly 20 years old. The bit-depth for samples is 8. Sampling resolution doesn't matter as the idea of the format is to play back samples at different rates to create music. (By default you can't compress the samples either, however it's possible for your programmer to pull it off because the sound decompression needs to exist in the cell phone.)
So by today's standards, there's no way to do this. If you're willing to lower your standards though, you can fit a lot in 100k. One way out of this is going chiptune, using instruments that sample for example one cycle of a basic waveform like square, sine, triangle or saw. Very basic, but it gives you, space-efficiently, instruments that sound like old computers and game consoles, which is what all the hip kids are into.
Combine that with some snappy percussion samples and whatever and you might very well have a stylish retro-induced music piece in your hands, ready for submission.
Here's the real space saving tip:
If you need to have three pieces of music like in your example and you are going to use pretty much the same instruments for all of them, don't make three separate modules because that leaves you with three 33k limitations to work with. Instead, make one module that has all the three parts separated as subsongs. That way you won't be wasting space on the same samples several times and you can have more and/or better quality ones in the single module file. This is done with loop commands.
Intro: starts at the beginning of the module, a.k.a. Order 00
.
. The song progresses
.
. And reaches its end on say, Order 04.
On the Pattern at Order 04, you insert the command B00 which sends the playback back to Order 00. Voilà, you have a looping intro music sequence.
After that you continue by writing the Win song starting from Order 05. If you don't want this tune to be repeated but only played once, you can trap the playback on an empty, silent pattern.
Win: starts on Order 05
.
. and it's a short one in this example and it finishes on Order 07 already.
. A silent pattern follows the music on Order 08.
On the pattern at Order 08 you can set a loop to itself, B08, which prevents the playback from playing the Win music again, or any of the other parts until a game state triggers playback on another Order.
All of this subsong stuff should be discussed with the programmer because it's not going to work automatically. The programmer has to become involved with the music replay enough to be able to jump song positions based on the happenings in the game. It may not sound that attractive but the advantage (especially when working with tight size limits) is too great to ignore without consideration. (I know, I've once successfully convinced a producer of this exact thing.)