The best "parallax scrolling" I've seen is in Battletoads. (Note: Battletoads is NOT MMC3 but...) One of the features MMC3 adds is a scanline counter. This allows different vertical portions of the screen to have different horizontal scroll values. (Split screen scrolling as described in Megaman 3 above) On the title screen of Shatterhand don't press start. Eventually you'll see an enemy shooting, and a guy will pan in from the right blocking the bullets with his arm. That's an example of this. It's not exactly as wonderful as parallax scrolling with different background layers though.
You might want to see Metal Storm then. It has actual parallax, and sometimes even double parallax (level 3-2--go play the game if you want; it's a lot of fun).
probably the most impressive, Mitsume ga Tooru