FreeOrion

First thing to do is add the import sys at the top, and the print(sys.path) in initFreeOrionAI(). No recompiles needed.If bastion can get the AI scripts to run by moving them, there's no need to add new C++ code to call or execute a Python function to do that; the AI script initialization can do so itself.

You're right again of course. This actually makes things much easier
May I suggest a slight improvement for that? Because, especially if you have long pathnames, the output in the logfile is a bit of a pain if you want to check which directories are included. So I made some small modifications to use pprint instead of print, and the result is definitely easier on the eyes

Patch for FreeOrionAI.py attached.

No compilations needed, as Geoff already pointed out, just some small additions to FreeOrionAI.py. To make things easier for you, I've attached a zip file containing a patched FreeOrionAI.py. Replace your FreeOrionAI.py with this patched one (make a backup of yours first), run a test game and post the logs. This is probably the quickest and simplest thing you can try before doing something more elaborate.

Quick test with Vezzra's patch:
Seems like it's getting interpreted somewhere without properly escaping the backslash, causing \0 to turn into a null character.
In that case all folders starting with characters from here http://docs.python.org/reference/lexical_analysis.html#strings (most notably \f = ASCII Formfeed (FF)) might cause problems.

Ugh. Well, I'm not going to try to fix that before a release. So as above, I suggest installing into a more-regular path like D:\Games\FreeOrion.

Yes, that was my first thought too. Fortunately it isn't as bad as it looks
After looking into the matter I tend to disagree here: This bug is quite serious, I wonder why there haven't been more people running into this problem on windows. To illustrate this let's take your suggestion for a more-regular path above: "D:\Games\FreeOrion". That one would work. But let's assume there is some guy who decides to use this path instead (the difference is really minimal!): "D:\Games\freeorion". This would turn out as "D:\\Games\x0creeorion" - uh-oh. The cause for this is the way string literals are handled in python, bastion already provided the link to the corresponding section in the python documentation in his post above (I won't quote the entire section here). As you can see there, there are quite some characters affected by this escape sequence parsing of string literals...

I don't think you want an unresolved issue of that kind in 0.4, do you?

Fortunately, going through this part of the python doc also gave me clues how to solve the problem. The code section in question is this one from PythonAI.cpp:
The path to the AI modules is inserted as a string literal into the command string passed to exec, ergo being treated as such by the interpreter. This isn't a problem on platforms that use "/" as the path delimiter, but becomes a big one on windows, where "\" is the path delimiter. However, python allows you to prefix string literals with "r", which causes the interpreter to skip the escape sequence parsing for the most part (details see link above). So putting a "r" before the string literal constructed with AI_path should solve the problem:
As I'm not able to build FO on the windows PCs at my disposal, I can't test my theory. However, I've been able to simulate the issue in the python shell on my old windows laptop, and the results look very promising. As the required change is a very small one, I think it's worth trying And as this change shouldn't affect the functionality of this piece of python code on other platforms, it shouldn't even be required to split the section into platform specific code parts.

This is going to be the smallest patch to any piece of code I've come up and will come up with for the rest of my life. I mean, how I'm going to go below one character...?

Given how delayed v0.4 is, and how easily user-fixable and relatively rare this issue is, I'd probably have be ok with leaving it in...

I've upgraded to RC3 (includes removing RC2 and config.xml) and did some tests:

Installed to D:\Games\FreeOrion, AI works ootb. (boring )
Changing \default to \fdefault (both the folder and in config.xml) causes the AI (and only the AI) to not be found. (failure as expected )
Changing \default to \x64efault (\x64 = d) and copying the AI folder to D:\Games\FreeOriondefault causes the AI (and only the AI) to be loaded from there. (success )

Issues should be solved with RC4.