perhaps you should try
smartly using matrices
transforming nicely
You lost me there, would you mind elaborating on this?[/font]
Another general purpose "surprisingly easy" approach is to just add black bars as needed, and render at your own preferred size.
This works nicely even on windowed environments, not just full screen. If the display window is too wide, draw it as maximum height and put black bars on the sides. If it is too tall, draw at maximum width with bars above and below. Keep your game in a floating point 0.0 to 1.0 size so you'll still be able to access each individual pixel for any size screen currently imaginable.
That sounds reasonable, but I'm a bit worried that if we use the "minimal screen area" (that one which will be visible on all resolutions) and add black bars on all larger screens, we will effectively see black bars on almost every device. Guess it's okay though, the user will probably not notice and it doesn't really matter whether I use black bars or more of the background image, the space can't be used for gameplay anyway. Technically, the solutions are very similar, I just have to center the background vertically.
The 0.0-1.0 based positioning idea sounds really good to me, guess I'll do that. Less confusing than to work with a reference solution. But I will also see if Android's density independent pixels do the trick for me, because I won't be able to use the former in layouts.