After more discussion, it appears that this change is too incompatible to be done in a single release.

Therefore, I propose a long-term change into this direction, with the actual change not happening until 3.5.

For the change of the python.exe location, I propose to add a key to the registry, say, "BinaryDir", which is added to 3.3 and later. Adding it to older installers is not useful, IMO, since people still need to implement a fallback logic. In 3.3 and 3.4, this will point to the toplevel directory, and in 3.5, it will point to the bin/scripts directory.

Now, for the change from scipts to bin, I don't have any good solution. Proposals, in particular including registry keys, are welcome. Symlinks are out as they require admin privileges. Testing for the presence of some directory might be an acceptable solution.