take the video card out again and blow out the pci or AGP slot and then reseat the card really good. also make sure that the mem is seated well (which it probably is since you've had it out testing other stick and all).
also, check in BIOS to make sure all is set right with settings. Is that an AGP or PCI video card? make sure those settings are right in there.
though if it's not hardware, I'm still leaning heavily toward video card drivers. Are there any other driver sets you can try?? maybe omegadrive has something.... are you familiar with omegadrives drivers? he has done some really great things. check out www.omegacorner.com
and see if you video card is supported by his driver sets... also check out www.ati.com
for any new(er) drivers....