Pertinent specs:
Athlon 64 X2 3800+ (2.00GHz, 512Kx2)
1GB DDR2 SDRAM at 533MHz
19 in (19 in viewable) 1907FPCFlat Panel Display
256MB nVidia GeForce 7300LE TurboCache
160GB SATA II Hard Drive (7200RPM)
Microsoft Windows XP Professional,Service Pack 2, English
16X DVD+/-RW Drive
Sound Blaster Audigy MB Audio

I should also note that on the previous computer I played this game, I experienced this problem to a lesser degree, but it would also resolve itself and play at normal speeds sometimes as well. This was independent of the number of simultaneous applications running at the time.

I've used CPUKiller before, but only for old DOS games which are actually processor speed dependent. I've never encountered a Windows 95 and up game that was programmed so poorly as to be directly dependent on flop rate.

If there was a utility like that for the video card, that may be more applicable. Deus Ex probably didn't predict a video card with dedicated memory, but then again I would hope it's not something so trivial as that.

Game settings are as follows:

Resolution 1280 x 1024
32-bit texture details
Everything cool turned on