I have used an FX-5500 with 256 MByte and had success as of late.
There was also a problem of stuttering which has only been recently fixed in xine-lib packages (around the last few months). The package I am currently using is xine-lib-1.1.2-r2.
Later Nvidia drivers work better too, such as 8762 but I cant remember what it was that works better ? (was something to do with TV-out I think)
The benefits are well deserved as it can take a little setting up to get XvMC running correctly
Here is a link to my machine with and Athlon XP 2500 and FX-5500:
As you can see CPU resources are quiet low at 22 % for a High Definition Signal. CPU resources with out XvMC are around 65 % with slight De-interlacing , heavy De-interlace goes well up and probably over 100 %
De-interlacing only had 2 positions with XvMC from memory, (On or Off) as that is handled by the GPU
Another experiment tried was Over clocking the FX series GPU and Graphics Memory with "Coolbits" , this from my memory had no effect on the MPEG Hardware decoders in these cards.
I did have a 128 MByte FX5200 which I feel ran the same for these applications.
Good luck with it