For me parallax scrolling is a feature which really makes a game feel retro and better looking at the same time. I'd like to use it for my next game, but it is going to need levels which not only move horizontally, but also vertically.

And there I have a problem, I can't see how that would work too well. There is the one level in Shinobi 3 which was vertical but also was just vertical.

Does anyone know of any examples of games with parallax scrolling in which you could move both vertical and horizontal. Im especially looking for hints on the foreground layer.

With two planes total :

If the background is 1 kilometer far (ex: mountains), it will not look odd if you scroll one screen up and this "horizon" doesn't change.

However, if this background is supposed to be close to the foreground plane, you should scroll it up a little whenever you scroll up. For example in a giant forest, if the foreground total playground is 2 screens high and represents full trees from roots to treetop, you may want a background picture that is 1.5 screens high, if the background scrolls 2x slower. This background would represent similar trees, drawn smaller.

It all really depends on what you want to draw (and can draw:) )