I have a GeForce2 MX400 card, and have experienced exactly the same problems. I inherited the system from my friend, and he told me that he had no similar problems when playing FPS games (I'm getting the same problem in Deus Ex, Unreal Tournament and Quake III Arena) but he had an S3 Savage 4 graphics card at the time.
Now I thought that it was a graphics card issue, and I thought I was overstretching the card running it at 1024x768x32bit colour, but even when I knocked the resolution down, I still got the problem. Like you, I thought it could be memory because the only other real difference, apart from the (lower spec) graphics card my friend had was that he had 192Mb RAM.
I've since uninstalled my graphics card drivers, reinstalled DirectX 8.1 and then installed the graphics card drivers again, and this has improved the performance! However, in a particularly frantic game of Unreal Tournament the other day, I noticed quite considerable chopping of the graphics in the way you described, but only when the action became really fast.
I'm running version 23.11 of the Nvidia drivers, and my system spec is this:
Windows 98SE
AMD Duron 700MHz
Gigabyte 7IXE4 main board, Bios revision F9
128Mb RAM
C: 20Gb WD200BB 7200rpm ATA100 (running in ATA66 mode)
D: 8.4Gb WD84AA 5400rpm ATA66
TEAC 540E CD-ROM drive
RICOH 7083A 8x8x32 CD-ReWriter
Nvidia GeForce2 MX400 64Mb
Sound Blaster Live 5.1
Zoom V.92 PCI modem
TRENDnet TE100-PCIWN NIC
My friend suggested that the 'stutter' being experienced may be the PC accessing the hard disk because there wasn't enough memory available to fulfil the requirement of the game at that particular time, so maybe 64Mb more would do the trick.
Like you, I have checked all the driver settings and Anti-Aliasing is off, so short of tweaking the settings (which probably shouldn't be necessary as neither of us have a particularly poor set up) I can't think of what else to try.