Whenever I reveal an enemy's cone of vision, the game stops running smoothly, you can immediately tell that the frame rate drops significantly.

Does anyone else suffer from the same problem?

It seems that the issue is driver-related (I've stumbled upon a few old (pre-2008) posts on various forums suggesting reverting back to old drivers).
I've tried pretty much everything - D3DWindower, MS Compatibility Toolkit, VirtualBox... while disabling hardware acceleration or emulating DirectDraw seems to fix the "slowdown" problem, it causes visual artifacts to appear, as depicted in the screenshots provided here:
http://www.gog.com/en/forum/robin_hood_legend_of_sherwood/the_game_running_slow/post12

I'd appreciate any help, both Desperados and Robin Hood are pretty much unplayable/boken in their current state.

Good news! The solution provided by Danny252 seems to have fixed the problem.
http://www.gog.com/forum/desperados_series/desperados_runs_slow_on_windows_7_x64/post6