Thanks bud. I'm not actually looking into a .mid format, but rather my own format, as this will be a multi-track sequencer, and not a midi-player. Of course, with time I could make it export .mid files.
I'm getting the Arduino MEGA, so I have more memory and more I/Os for other things, that I plan on using on another project. 
And yes, SD looks the way to go, I'm already aware of the memory limitations of the Arduino.
Thanks again. Best Regards, WilliamK