I've abandoned it since there's plenty of better scrolling shooters out there already, but I got my "ITAD S.G." project working at IIRC 30 FPS @ 500 MHz:
It's even faster when overclocking to 800 MHz, about 45 FPS, I think. It uses software rendering; I haven't tested to see if hardware rendering would be faster or slower.
I believe Rescue is also in Python, but I don't know the specifics of it.
EDIT: Just looked at using hardware acceleration in ITAD S.G. The difference in speed is negligible, but it seems it's slightly slower than software rendering.
I made The Lonely Tower. And I packaged BubbMan2. And helped a bit with Which Way Is Up and Sparks. I've heard that some of these run very slowly, but I have no Pandora for testing.
My Rebirth entry (Wicket) was in Python/PyGame. Was running smoothly but wasn't really demanding. Whole screen scrolling was a bit tricky to get smooth.
Thanks for all your answers! I will take a look at the different projects you mentioned to get a better feeling as to what is technically possible with pygame