To be honest, I find the musical software you're using is limiting you. Why not use a free MIDI maker, that actually gives you a lot more freedom? It might not be "professional", but you need to start somewhere when making music. And I don't think Mario Paint is the best place.
I use Anvil Studio, and it hasn't failed me to this day (except in the rolling for notes, lol). And if I'm not mistaken, it might even be similar to the Mario Paint, except without the happy symbols.
Can Mario Paint not do sharps and flats? I can notice that flaw very, very much. Adding in a higher/lower note at the same time does not fix the problem.
Nope, no sharps or flats. I use normal midi editors too, and my work is decent, but as strange as it sounds, the more limiting the program, the cooler it is when you pull something off. Part of it's just poor song choice on my part though. I have Vampire Killer (only 2 flats in the whole thing) that I'll upload once my internet works (I'm on my Wii now). Besides, this whole Mario Paint thing is just a hobby.
I can honestly say Brinstar's my worst one, and I learned from that. My Ninja Gaiden one came out really well, and so did Zelda 2 Cave (once I can upload it >.<).
There's a classic Peanuts strip where Charlie Brown notices that the black keys on Schroeder's toy piano are just painted on. So how does he play all those complicated pieces? "I practice a lot."
And apparently, some people practice a lot more than they should. (note: not me) Here's my two more recent works (internet works again, yay!) that came out a lot better from a 'accidentals don't sound like crap' standpoint. Vampire Killer Zelda 2 Cave