Have you disabled DEP?

DEP is enabled. But I tried turning it off to see what would happen, and it still crashes randomly.

Side note for anyone who happens to stumble here through the desolate wasteland of Google Results; after doing a full install, make sure to manually copy the file "lemmings.box" from your CD to your install directory, overwriting the file that's already there. This is necessary because the installer corrupts this file. If you don't do this, then when you get to the level with corrupt data (specifically 9-6: The High Dive), you're going to have a bad time. The patch notes say to do this, but I didn't read them until after nearly an hour of desperate searching.

Well, something interesting just happened. I played a session without a single crash just now. I'm on the last set of levels, usually on this set it crashes at least twice per level (every retry has a chance of crashing, and a lot of retries means a lot of crashing). I beat three levels without one crash.

Either something's different, maybe a Windows Update, maybe Intel's predictive execution was being crashy, or maybe I just got lucky today. There's five levels left before I beat this game. We'll see if it continues to behave next time.