Thanks. I played both of these ages ago and didn't remember that either had parallax scrolling. Particularly Lionheart has some really nice BGs. In terms of style they come pretty close to the kind of stuff I'm looking for.
timppu: On PC Jazz the Jackrabbit 2 comes to mind, especially as it did it in hires.
http://www.youtube.com/watch?v=OTZOrw7unKk Oh yeah. Now that you mention it - I particularly remember a level called "Victorian Secret" or something and it's actually due to the backgrounds. Thanks for reminding me. :D
timppu: On Amiga, I am sure there are bundles of examples, but for some reason I remember Starray specifically from its smooth parallax scrolling, even if it was mainly restricted to the lower part of the screen (ground).
Wow, thanks! I didn't know this one. Pretty nice example, despite the limitation to the very bottom of the screen.
Sazanamistyle: The Donkey Kong Country /Super Donkey Kong trilogy on the SNES/SFC was brilliant for this.
Indeed, thanks. Particularly the snow storm seems brilliant.
Wishbone: Funnily enough, as soon as I saw the thread title, this is what I thought of :-D
I'd like to say "well duh, that's because it's the best parallax scrolling ever seen in any game!" but I guess that's not really true. Well, it will always have the best parallax scrolling in our hearts, it seems.
Thanks for the many suggestions so far!