Not sure about the latest versions of Maya, but I've run Maya 4 up to Maya 2008 on XP with an old AGP-slot MSI Geforce TI4200 card, soft-quadroed (with Riva tuner) up to a Quadro4 700XGL. Soft-quadro is an old mod that patches or unlocks the quadro drivers that were included on older cards. It can be a pain to set up but works once it is. I use it with max 2009 as well.
Like Gect mentioned...what's the budget? What type of card slot? You could pick up a Quadro FX 1700 if you have PCI express slots...not the cheapest but not uber-expensive either.
"Terminat Bora Diem, Terminal Auctor opus."