I've received a few more e-mails and blog comments containing input and information about the famous DirectDraw palette problem which messes up colors in older games.
In particular, Windows contains compatibility entries in the registry, and Jari Komppa has written a ddraw.dll which wraps DirectDraw.
I've updated my blog post from 2009 once more to reflect this new information. Currently, the easiest way to run Age Of Empires 2: The Conquerors without any hassles still seems to be my tool, which you can find there as well.
P.S.: Also, I will be competing in the Google A.I. Challenge again this year. I look forward to seeing you there!