As far as I know the registry key is a supplament and not a requirement for a correctly functioning python.  There is an entire PEP about the registry keys and what to do with them...I'm not sure what the current status is on 2.7, but like I said, I believe that lack of registry keys should not keep python from working if it is installed correctly.  Python uses other methods to find its library.  Since you are in an embedded scenario, this probably means that there's something about the environment and/or disk layout that you haven't set up in the way that python expects it to be set up.  You migth try asking on python-list or the #python irc channel on freenode for help.  

I'm guessing this means there's something missing from the ebedding docs with respect to Windows, so I'm going to leave this open until that is confirmed or disproven :)