Just spent half-hour figuring out why PHP does not want to run shell_exec() command. Might as well write it down here for future reference.
Go to IIS -> Fast CGI settings:

There select your PHP application, click Edit on right hand side.
Then expand Advanced Settings and change protocol to TCP.

Save and DONE!