I have a conflict with the poll, as mp3s actually sound like the old-school sounds, coming right out the snes:
Why not use low kbps mp3's? Sounds better, and much more like the original than the assembed midi output of the computer.
The midis dont reference the same sound library as you want them to, and so sound horrible, and use more cpu time than youd desire We're on pcs not a snes: sacrafice memory for speed. Anyway, a streamed mp3 wont use up much ram at all, only backing storage=>increased download time.
Although im a strictly mp3/ogg/(anything better than midi) person, you *could* offer an alternative download and so use both. Ie program searches for mp3 folder at startup, and if its not there will use midis throughout; If it is there, use the mp3s in that folder.
[edit]
The top two voted games in the zfgc 2005 game competition were the only mp3 users: They sounded and felt more authentic, and that was their strength: To have the atmosphere and feel like the game. They scored something like 1500 and 1400: the others at scores like 700, 500, 300, etc, which was kindof shocking as the mp3's were the only majour difference. (Well..higher framerate than some of the other very good entries, which was again to match the atmosphere of the taget zelda influence).
[/edit]