The NES (and most early consoles) ran at 50/60fps, not 25/30fps. It achieved this by ignoring the PAL/NTSC spec and sending all the fields at the same polarity instead of alternating odd/even fields. This halves the resolution but gives you double framerate progressive scan video, which is a good tradeoff for games.
The traditional game console solution for PAL consoles was to just have letterboxing with the extra 100 lines blank, with everything vertically squashed a little. Games usually didn't compensate for the lower framerate, so just ran slower.
PAL console gaming was a GREAT experience, as you can imagine.
Things got better from the Dreamcast onwards as they could software switch to 525 line / 60Hz modes (usually with PAL encoded colour for composite video, except for the PS2 which used pure NTSC), and it's all now moot with HD.
(PAL tvs had 100 more lines and refreshed a little lower 25, vs NTSC's 30 frames per second)
Seems like it would be a pain to make that work. Knowing the pain of PAL <-> NTSC tv conversion.