Just a disclaimer: I don't have GOGs version of LoM, (though I have bought many games from them, of course :) ) just my CD version of the Special Edition. But I've gotten good advice on GOGs forums before with non-GOG versions so...

I got the urge to play this old classic and seeing as I have a spiffy new laptop, I figure now would be a perfect time. But as soon as I got onto the overworld map I was getting this strange lag. It seems to affect mainly with scrolling where it will scroll jerkily and continue scrolling a second after I stop. I tried the unofficial patch but the lag persisted.

Any advice would be appreciated. I really want to play this old gem.

Thanks.

Have you tried running the game in compatibility mode (e.g. Win XP or Win 98) yet?

Hmm.. Changing to Vista compatibility of all things seems to have helped a bit, though its still a jerky. Any other ideas?

I had exactly the same problem with Lords of the Realm 1 and the solution was to restrict the cursor to the top left 320x200 pixels (which is the resolution of Lotr 1). I used autohotkey to do it.

Check the solution I described here. Maybe it will work for Lord of Magic too.
http://www.gog.com/forum/lords_of_the_realm_lords_of_magic_series/erratic_cursor_movement_cd_version_of_lotr_1

(instead of 320x200 use whatever resolution Lord of Magic is using).
If you need more help, let me know and I'll share my ready file with you.

Try Ascension64's unofficial patch for LOMSE.
https://www.dropbox.com/s/mfjz8bdshx9x0vi/LOM%20Map%20Collection%2017.06.2013.rar?dl=0

Also you can try Mantera's GS5 Mod, a very good extension to the game potential. It also provides an ability to control the scrolling speed. You can find the community here:
http://impz.proboards.com/