both great suggestions. if you can spring a little more (~$300) a 6800GT will go a long way (especially if you get a 256mb version). x800xl agp is (Best Buy is $349) $50 more than pci-e but is also a great card. these are both 1 tier up from your budget but a vid card, imho, is worth it...depending on how much gaming you do. either of these could be overkill as well.
so what are your primary concerns/uses? seems like gaming if it's an a64. if so then don't skimp on vid card.
btw, i think you mean an A8V not K8V for the mobo if it's socket 939.