I'm developing on Windows, and I've searched everywhere without finding anyone talking about this kind of thing.
I made a C++ app on my desktop that embedded Python 3.1 using MSVC. I linked python31.lib and included python31.dll in the app's run folder alongside the executable. It works great. My extension and embedding code definitely works and there are no crashes.
I sent the run folder to my friend who doesn't have Python installed, and the app crashes for him during the scripting setup phase.
A few hours ago, I tried the app on my laptop that has Python 2.6 installed. I got the same crash behavior as my friend, and through debugging found that it was the Py_Initialize() call that fails.
I installed Python 3.1 on my laptop without changing the app code. I ran it and it runs perfectly. I uninstalled Python 3.1 and the app crashes again. I put in code in my app to dynamically link from the local python31.dll, to ensure that it was using it, but I still get the crash.
I don't know if the interpreter needs more than the DLL to start up or what. I haven't been able to find any resources on this. The Python documentation and other guides do not seem to ever address how to distribute your C/C++ applications that use Python embedding without having the users install Python locally. I know it's more of an issue on Windows than on Unix, but I've seen a number of Windows C/C++ applications that embed Python locally and I'm not sure how they do it.
What else do I need other than the DLL? Why does it work when I install Python and then stop working when I uninstall it? It sounds like it should be so trivial; maybe that's why nobody really talks about it. Nevertheless, I can't really explain how to deal with this crash issue.
Thank you very much in advance.
In addition to pythonxy.dll, you also need the entire Python library, i.e. the contents of the lib folder, plus the extension modules, i.e. the contents of the DLLs folder. Without the standard library, Python won't even start, since it tries to find os.py (in 3.x; string.py in 2.x). On startup, it imports a number of modules, in particular site.py.
There are various locations where it searches for the standard library; in your cases, it eventually finds it in the registry. Before, uses the executable name (as set through Py_SetProgramName) trying to find the landmark; it also checks for a file python31.zip which should be a zipped copy of the standard library. It also checks for a environment variable PYTHONHOME.
You are free to strip the library from stuff that you don't need; there are various tools that compute dependencies statically (modulefinder in particular).
If you want to minimize the number of files, you can

link all extension modules statically into your pythonxy.dll, or even link pythonxy.dll statically into your application
use the freeze tool; this will allow linking the byte code of the standard library into your pythonxy.dll.
(alternatively to 2.) use pythonxy.zip for the standard library.
C++ with Python embedding: crash if Python not installed