I assume you're using AA from the NVIDIA Control Panel. I'd try going through the different AA settings like maybe 2x, instead of the highest setting. You might also try using different graphic drivers to see if they give a better result.
Unfortunately, though, I don't know if you'll be able to get it to work right since a lot of the older games were never designed for AA and thus can have real problems when you try to force it. I remember getting The Longest Journey to look good with AA, but then the background would sometimes bugger up on me.

AA does that sometimes for some odd reason. I hate to tell you this but you may just have to live without AA. If it's that big a deal check out the mod thread in this forum for a mod that updates all the graphics.