Deus Ex is pretty demanding indeed, although when I tried it on a Voodoo3 , the game was playable high detail/1024X768, and that was with a 700Mhz Pentium3 , the framerate usually stayed in the 30s . with some slowdown. Thankfully the game is fairly slow paces so it doesn't need a blazing fast frame rate to be enjoyable.
The best (released) card to play it on is of course the V5500, The card will give you 55-65fps even at 1280X1024 (thats from personal experience) , as long as you have enough CPU power to feed it (Im using an Athlon 1400 , but that P4 should be fairly equal to it).
That said, the Voodoo3 still gave me a better overall result than the Geforce2 Ti , where at the same resolution, the game was often around 10 frames lower (fair enough I did enable 32bit colour, but given that one expects the GF2TI to wipe the floor with the V3 , thats still a disappointing result)