It's really weird then. Not sure what else to look at. Does anyone know whom to ask about the changes they made (i.e. GOG developers)?

I made a hexdump of Saboteur.exe file (using xxd). Then grep that text file for map entries and I found worldmap entries there. I don't own the retail non-GOG version to compare.

I'm suspecting the following:
1. If there are specific GOG registry values, they should have been set during the installation.
2. There have been offsets in the exe file. For example in the way for widescreen support for other games (Dungeon Lords comes to mind).
3. Initially the cause of the problem was the video drivers and it could be solved by using older ones. Maybe the problem appears on Wine, due to the way it handles (or doesn't) the video drivers.

I think the last option is the most probable.

The thing I don't understand. According to @JudasIscariot at least, when changing the config.ini manually on Windows, the map bug is present. When it's changed with the tool, the map bug doesn't show up (on Windows). That suggests, that tool modifies something, to match selected resolution, and that something is more than just config.ini. But so far we didn't manage to identify what it modifies.

You can do the same test - modify config.ini manually to something else on Windows, and check if the bug shows up.

I still suggest someone to use Process Monitor and trace all activity of the video settings tool, to catch what it does. If no one can do it, I might end up finding Windows copy and running it in VM just for the test purpose.

I'll check again.
I used regmon tool for Windows XP. It's possible that something could have passed unnoticed.

I'll try to edit the ini file manually too.

It could be modifying some weird file somewhere. Filemon might help for that.

I have no time for monitoring the system now. But I just edited the config.ini file manually and I have some interesting results!

First of all, the native screen resolution is 1920x1080@60Hz. That was the resolution the game was set on.
Also, I should note here that my drivers are set to stretch the image to fullscreen (no black bars around it).

Here are the steps:
- I used the VideoSettings.exe application to change the resolution to a small, non-native, 4:3 one. It was 1024x768.
- Started the game. The map zoom was incorrect. The bug was there for that resolution!

- I edited the config.ini file manually. Set the resolution to 1920x1080.
- Started the game. The map zoom was fine. No bug was present.

So, I think GOG has injected offsets to the .exe file, and there has been no real fix for the cause of that bug. As a consequence the problem on wine is due to the way it handles the drivers (no stretch allowed by principle on wine).

OK, so we can exclude the tool, it's not relevant to this issue. I just tested both 1920x1200 and 1920x1080 in Wine. Both are messed up.

May be someone can compare GOG current binary and one they first released? Those resolutions might be hardcodable in it somehow. Something like that works for example for Star Wars: Knights of the Old Republic II.

If you are interested you can try and get a trace showing the map zoom with (you want the one with [url=https://people.freedesktop.org/~jrfonseca/apitrace/]xp in the name). It should help with what calls are being used. It isn't always able to get a proper trace. You would trace it under XP and then play it back under XP to see if it shows the zoom correctly. If it does then try the trace under Wine.

So, with Wine Staging 2.9 all three games are platinum for you? Clean prefixes, zero overrides, no graphical glitches, etc? Also, with the quick look did the FPS still seem fine?

Oblivion - Wine Staging 2.9 gold
Fallout 3 - Wine Staging 2.0 gold (totally playable, but some graphics settings either don't work or cause graphical glitches)
Fallout: New Vegas - Wine Staging 2.0 gold (about the same as Fallout 3)

Some systems may require an override for winegstreamer to prevent frequent crashing. Oblivion had some graphics issues (most obvious with the fog/mist effect in dungeons not looking right at all) with Wine Staging 2.0 so I used 2.9 instead for that.

Elder Scrolls IV: Oblivion - Game of the Year Edition Deluxe

...runs perfectly with Wine (I use Wineskin with Wine 2.3) on Mac OS X. The only thing is to replace the c:\windows\system32\d3dx9_27.dll from the Wine installation with the same dll from a normal Windows installation (for example WinXP). Then the main character gets a normal skin color (this is an old Wine bug https://bugs.winehq.org/show_bug.cgi?id=20074).

Thanks. If you could note for each entry whether you have videos working or not working it will be appreciated.
Staging actually has a patch for DXTn textures. Not sure if that's all you need on OS X (Linux may need some additional system lib). Otherwise using the native version, as you noted, works. For that you can simply do winetricks d3dx9_27.

Game: Pharaoh + Cleopatra
Installer setup_pharaoh_gold_2.1.0.15.exe

Distro: Linux Mint 17.3 KDE 64-bit
Kernel version: 3.19.0-32-generic
Graphics card: ATI HD7660G (Laptop integrated with A10-4600M chipset)
Graphics driver & version: Propriatary fglrx 2:15.201.2-0ubuntu0.14.04.1
Wine version(s) tested: Wine 1.6.2

Install notes: Install & play

Installs with no problems.

To play, the desktop resolution needs to be set to the game's resolution or the result is a black screen. A way round this may be to use a widescreen hack from wsgf (details here if you need them https://www.gog.com/forum/pharaoh_cleopatra/widescreen_patches). my native resolution isn't supported by any of them so I can't test fully, the hack I used runs fine, though I still have to change desktop resolution.

First, thanks. Needs a bit more work. The format should be e.g. either post #35 or post #855. Both the file hash for the installer and AppDB link (set to none if it doesn't exist) are non-optional. You appear to be going for the second format. Please make use of the bold tags. This has an AppDB link.
Did you test playing vanilla install or just the widescreen hack? Widescreen hack should also have a file hash for whichever version used. Additionally list in brief all steps needed to run the game in widescreen.
Lastly, Wine 1.6.2 is vastly outdated. Believe this game runs well in newer versions of Wine. Official WineHQ packages are available for Mint 17.x. Stable is currently at 2.0.1. Devlopment & Staging are 2.9. Last old Stable is 1.8.7. Something closer to them would be more useful.