Gonna pick this up, here's what I've got so far. (the sound is correct, there is no music)
Link to video
The first level is much different than the RTA route, and I haven't tried it yet but I'm 99% sure this is faster. What happens:
The potato soldiers are spawned on the upper platform. You actually need to see them to get them moving, it's not possible (but would be faster) from directly underneath. Getting the extra pellets here doesn't cost any time.
Hitting one of the potatoes when they're exactly on the edge of a platform causes one to fall off.
I waited for it to come back to life and guided it to the edge of the map. Hard difficulty is actually MUCH faster here because the respawn time is shorter.
Dying on the edge of the map and falling to the right tricks the game into thinking you're outside the level boundaries and just gives you the exit.
I will investigate some more to see if there's a faster way to do this. Also, supposedly there is a pellet duplication glitch but I couldn't get it working (either fooling around in DOSBox or actually TASing the fastest possible tosses).
WIP 2, featuring a faster Horseradish Hill and a couple more levels.
Link to video
I get the key in Melon Mines because it's actually faster than getting the one outside of Castle Tuberia (by only about 1.5 seconds though!)
Spud City is quite long but has 6 bombs in it. The Frenchies have some funny behavior where they won't attack if you're too close, so you can run along with them if you want. One of them is used to get another death exit.
I wonder as well. It seems the Frenchie is the best enemy for the job because it moves quite fast, it's just a matter of getting it to behave. I tried stunning it and walking ahead but it turned out to be quite a bit slower. If only I could make it turn around sooner...