It seems that the CreateProcess() Win32 API expects the explicitly-passed environment variables, if any, to be in alphabetically sorted order. It is documented in passing in the API description, but you have to really look out for it to notice it. Without doing this, you might find that the spawned process is not able to retrieve some of the environment variables you are passing to it. This also seems to affect programs spawned using Runtime.exec() in Java, so even if you do not work on Windows yourself, you might want to keep this in mind for your hapless users.
Thanks to Saju for the explanation and to Rahul for bringing it to my attention.