I found that your settings given at that link above, for Super Mario All Stars, arent the best you can use.
Here is what I've tested.
- Frameskip = 1
- Auto Frameskip = OFF
- Screen Size = Normal
- Show FPS = ON/OFF doesnt affect it either way, but you'll see how the rest of the settigs effect the gameplay with this turned on
- VSync = OFF
- Sound = ON
- Sound Rate = 22khz
- Graphics Speed = 1.0x
- Sound Speed = 1.0x
- PSP Clock = 333mhz
With this config I average 50-56 FPS in Super Mario World. Super Mario 2 runs at 45-48 fps, but it seems like its full speed. Super Mario 3 still runs a little slow, coming in at 42 fps, which lags a LITTLE. Still very playable though.
You should probably retest your settings on those games listed already. Turn the sound settings to 22khz, put the clock speed on 333mhz for all of them, and adjust the screen sizes for better framerates.
I'd start with a Normal screen size, and go from there. The goal is to make the game run as fast as possible without having to use frameskipping at all.
Update:
Here are some settings for super Mario 3, using the All Stars rom from below: * note that only changed settings from the ones above are listed
- Frameskip = 2
- Screensize = Fit
With these settings, combined with the settings above, you average 53-60 fps with Mario 3... plays at full speed.
ops: 
Linear Mode
