Interesting,
First of all, your problem with america's army is not uncommon. It is interesting to note that the radeon 7500 is not supported for this game but the radeon 7000 and 7200 are supported. I looked into it a bit over at the america army tech support forums and found that this issue has cropped up with other users trying to play that game. They suggest everything from making sure you have the latest video drivers, motherboard drivers, and sound drivers for your machine and also that you are running America's Army 1.7, and re-installing the game after removing all previous traces of it from your harddrive. Some people have even gone as far as formatting and re-installing windows with varied success.
As far as dxdiag detecting the older drivers, that could be significant. Maybe when you installed the latest drivers the old stuff wasn't removed properly. I think if you completely un-install the old catalyst drivers, reboot into safe mode, cancel out of the installation process that occurs when you reboot, and then install the latest drivers, that could hopefully remove any trace of the older drivers.
Before attempting that, however, you could try out this program called
jvpowertools1.4 which has a registry cleaner tool that might help clear the trace of the older drivers. I believe the registry cleaner option is under tools and you should special select all entries that should be safe to remove after running it and before deleting entries. If you have any questions about doing that, let me know.
Now, the stranger part is the corruption within the Warcraft 3 menu and I have had little success finding much information on that yet but will post back if I do. Maybe you could take a screen shot of that so some of the more savvy video card experts around here could help decipher its meaning.
As far as the dxdiag tests go, I have looked all over for your specific message and have not found much other than what I have already suggested. Most of the time I have read that failing those tests is a driver/directx install issue and I may have seen somewhere that it could be hardware related. Sorry if that sounds vague.
Oh, and the madonion test, well I think it's a good thing you computer didn't completely blow up when you ran that. It puts signficant stress on the video card, especially the 7500 with directx9.a. You would see better results, possibly, if you went back to 8.1 and ran 3dmark2001se.
Finally, since this isn't affecting other programs, you may still be able to find a solution before determining that a new video card is in order. Granted, eventually you will need a new video card to run some of the newer games. If you aren't in any rush though, some other options on how to fix this might pop up and if I see them I will post them here.
Good Luck!