Quick shot in the dark, mostly because I've also seen strange problems with JA2.
Have you tried setting the game to use only one GPU instead of both? It is possible that Crossfire/SLI will cause the graphics to stutter.

I definately tried changing SLI to single gpu, even disabling SLI altogether. The game works fine on some computers and not fine on others. GOG support told me to install the june 2010 directx runtime package, but that did not help either.

I fixed my stuttering issue (which was only happening while windowed) on my AMD X6 based computer by changing the desktop color depth to 16 bit instead of 32 bit, however it didnt work on my intel laptop, which was stuttering at 1280x1024 as well as when windowed. I didnt try messing with the desktops resolution, but that monitor is 16:9 while all my other computers that worked fine were 16:10 - maybe forcing the desktop resolution to a 16:10 resolution like 1920x1200, 1680x1050 or 1440x900 would fix the issue?

I've no stuttering issues but the game seems to run top 30FPS (neither MSI AB, Fraps or PlayClaw won't confirm though). Is there a way to increase performance? I tried affinity, priority, comp mode XP, admin rights, the usual but nothing helped. I play at 1280x1200, the highest anyway.

Sorry for reviving this old thread, but if anyone still has issues with graphics/performance on win 7/vista...

First try switching desktop colors to 16-bit, which fixed things for me. If that fails, turn off terrain animations in the game settings - this is kind of painful, but it also worked for all my friends that play this game, so it's good as a last resort if everything else fails.

Reviving an even older thread, but I had similiar problem and the workaround was to change the resolution from 1280x to 1024x. This eliminates the stuttering completely for me. I hope that it will help somebody.

When I've installed the game on my Windows8.1, had the same problems with the performance (had no problems on Windows 7). I tried different compatability options, but it did not much. Using of DXWnd to run the game helped me out. Game runs smoothly in 60 fps with any resolution.

Did you use the template already present in DxWnd \export folder or a custom one?

I did a quick test with it, and while it runs OK in a 1280 window, I get tons of visual artifacts that makes it unusable

When I used DXWnd to run the game for the first time with the default preset of options, it worked perfectly. So I did not change anything. I play it with fullscreen 1280 resolution and no problem here. I did not try to run it with special template.
Some of the problems can be related to graphics card drivers or DirectX.

So, I reset my computer (initially it came with Windows 8). And the interesting thing is that GOG version of HOMM 4 runs absolutely without any issues (without using DXWnd) in any resolution mode. I did not set any compatability options. With updated Windows 8.1 had the problems described above.

I had same problem on W7.

When I tried to run Heroes 4 on Linux and Wine 3.0, it helps for me - the game works great with no any performance issues :)