hmm, that's very strange. There should be no problems with any of those versions.
Do you have all those versions on the same PC? I would have thought that trying to install different editions of the same major version of Excel would be problematic, but I may be wrong about that.
If you have them on different PCs, is it possible that some setup was different to where you're running 2007 successfully? For example, is the PATH set correctly (apologies if that's something you've already checked)?
When you said before about the versions of msvcr90.dll, presumably you were talking about 2007? Is that same dll installed on any other PCs you're using?
Going back to depends.exe - if you copy python27.dll to another folder without anything else in it, and then open it with depends.dll it should still find all of its dependencies. If it doesn't, that means you have you PATH set incorrectly and that will be the reason why PyXLL can't load it.
Sorry to keep coming back with more questions