JoachimBeinhart: Go to the folder where you installed Settlers 3. Locate the file "regs.cmd". Run it as administrator. After it finishes, you can run the game. I advise, that you run "setups3.exe" first, to set the screen resolution.
Geokinkladze: Yeah this doesn't work as people seem to keep saying.
While this is completely offtopic (this topic is about widescreen, not cd-keys): yes, regs.cmd cannot even work. That file only sets a "SingleNumber" intended for SinglePlayer and not a SerialNumber, that is needed for MultiPlayer. So regs.cmd will only work, when using the file s3.exe - but not when using the s3_multi.exe, s3_alobby.exe - or any other exe. One needs to use the actual serial key that can found under www.gog.com/account -> S3 -> More -> Serial Keys