I should have mentioned that you also have to remove the web.archive.org parts of the URL. Just wanted to point out that most, if not all of those ancient files that were archived by the Internet Archive back then are still lying around on
aoe.heavengames.com in the "downsnew" folder.
Normally, I would have posted a direct link to the file, but as far as I know, hotlinking ist not allowed.
Can you view the filenames for each of the non-working downloads? That would make it much easier to get hold of them.