Well, this is the strangest thing I have ever seen, due to the inconsistancy of PHP.exe.
Like I said, both CGI php.exe and ISAPI worked fine. Then php.exe stopped working.
Eventually, I found TWO problems. First, I had an extension which was not installed correctly, so the extension dll didn't load. Second, my cgi_force_redirect was ON, and it needs to be OFF on Windows.
The problem is, php.exe worked with those two problems before, so I thought everything was working! I have to say the behavior of php.exe is puzzling.