Did you finally find a way out ?
I'm exactly in the same situation as you are. Around 12000 MXDs that must be moved from one coordonate system to another.
I also intend to reproject on the fly thousands of shape files and rasters.
For this, I rely on a Python script. It's already able to convert shapes and rasters, but I havn't found the clue so far for mxd.
Your message gave me some hope.
As if that wasn't enougth, I run a 9.3 version of ArcMap. Arcpy is available since ArcMap 10 isn't it ?
Please let me know if you got through this, it could help me a lot.
Thank you