cubicu07: I'm running a Vista x64 here, no slowdowns except when I installed the high res patch. Then I removed ddraw.dll and the game runs at normal speeds. Oh. I also removed the compatibility settings on the exe. So try that too.
I applied the "sfall.zip" patch and that fixed the lag, but then I was having the black screen problem. I turned off the compatibility settings and it seems to be running normally now. Thanks cubicu07. It seems odd to me that having the compatibility settings turned on would cause a problem.
EDIT: So I totally lied. That didn't fix my problem. When I first tested it I was able to play for about 10 minutes with no problem, so I shut it off. Ever since, it's still doing the black screen though. One odd thing it's doing now is every time I turn off Compatibility Mode, it turns itself back on to Windows 98/ME. Any ideas?