Most odd, I will look into this some more. It seems like the game is not retrieving the available modes from the directx/driver and is falling back to the default.

Have you tried doing the above again and running the game from a terminal with the 'D' command line argument? Example:

cd /directory/where/game/installed/

"Medieval_TW D"

You should then end up with the game running in an overlay, with the bottom right of the desktop visible. See if any modes can be changed now?

Are both the battle map and campaign map restricted to 800x600? I say this because I think the campaign map is DirectDraw only whereas the battles are Direct3D - this problem might be something to do with the latest DirectX version.

Are there any settings in your nvidia/ati control panel you can change? Maybe turn off EDID and set a specific screen resolution (for example 1024*768), then try again?

Failing that a third party program like ATI tray tools or powerstrip may be of use, but not sure if it runs on Windows 7?? (I'm not a windows user these days so wouldn't know)