It doesn't seem to matter which Graphic Mode, Scaling Engine or Resolution I choose, the game defaults to it's standard resolution as soon as it runs.

Running on Win7 x64 with a Radeon HD 6950.

Anyone have any ideas?

If I recall correctly, the game had a set resolution in both MS-DOS and Windows 95 mode. The most you can do, if your graphics card supports it, is to stretch the resolution so it literally fills the 16:9 format for your screen. I've been able to do this on two computers, and it runs well in that mode. To do it, you'll need to go into the settings of your graphics card to do it.