I'd start with the Radeon 7200 - you can find these for less than $30, and they do MAME just fine. However, I'll agree with the approach that the others took above - if you expect to play more than MAME, you may want to spend the additional $ for a higher-end card.
The Xpert should work fine, but I would think thats the bare minimum - I had a 3D Rage II a while back that worked OK with normal resolutions, but hardware stretch would cause even basic games to stutter.
In terms of how old of a card you can use, this will be the limiting factor - some older cards do not offer hardware strecth, or take a performance hit with it enabled. A Radeon card handles these fine, and should offer decent triple-buffering support when they get it fixed in MAME.
As an aside, make sure you get a card that says "Made by ATI" or "Built by ATI" rather than a "Powered by ATI" card. The "powered" cards are 3rd party cards based on ATI technology, but their TV out quality is generally not as good as cards actually manufactured by ATI.