OK, not too technical here, so:
GFx Card NVidia GeForce 5900XT (don't think this is actually relevant)
Athlon 3300
1 GB RAM
3 GB pagefile (set min and max) (don't think this is relevant either, but don't try no pagefile)
Symptoms of problem: Game slows hugely until it takes forever to load and then crashes out with a variety of lock-ups after a couple of turns. Lock ups often result in partial (losing direct3d) or complete (monitor goes dead) GFx card failure. Problems seem to be graphics related. Problems do not occur in earlier stages (unless a lot of scrolling around is done). This was on an 18 person single player huge map.
Assumed reason for problem: The game is a memory monster. I believe that it simply runs out of operating memory. It doesn't seem willing to use the Windows pagefile - I assume it tries to use it's own cache for that.
Fix: Ram defrag. Get yourself a RAM defrag program (such as FreeRAM XP Pro from
http://www.yourwaresolutions.com - which I have been using). Start Civ 4, load up your game. Alt-TAB back to the ram defragger program, wait for the drive to stop thrashing and defrag the RAM (for FreeRAM, hit 'Go'). The available memory on my PC goes from about 100 MB to ovre 50% (>500 MB). Go back to Civ. The alt tabbing out and in takes a while so be patient, but when it comes back up Civ should run pretty well for at least half an hour. As soon as it starts to slow down, repeat the defrag process. Should keep it going. I was able to play on the high draphics settings fairly easily with this solution.
Thanks to an unknown person on the German boards for suggesting this solution, and to my German housemate for translating the suggestion.
Finally: Don't blame me if this doesn't work, but if it does and you see posts from someone with the same problems, provide the tip (or link to this post). And here's hoping for a patch to make all this fuss unnecessary.