Are you running the game under DosBox?
If so, chances are that your problem might be caused by your emulation of a Sound Blaster 16 soundcard. Under certain configurations, it can screw up the sound effects by playing them too fast. Switching the Sound Blaster emulation settings to a plain Sound Blaster card solved the problem for me.
If you're running the game under Windows without resorting to DosBox, you might to check your soundcard's settings (IO, IRQ, DMA and High DMA) and tweak with them a bit. I'm not aware of the configurations that run Lemmings 3D properly and not properly, but with some tweaking and luck, you should be able to find it.