I bet you didnt add it to the Web Service Extensions..
open up the IIS Manager (MMC)..
open your server
go to Web Service Extensions
click Add a new Web service extension
Name it PHPCGI or whatever you want.. and add your php.exe extension.. this will allow it to run in CGI mode (.exe) but it may slow down in performance (big debate on CGI or ISAPI)
restart IIS and it might work! 😉