It's been a long time since I admin'ed a Linux server, but I believe the biggest issue was the user account under which PHP is executed itself. If it was an account that had execute permissions for the root folder than contained the executable, i.e. /usr/bin, then they would run.
Seems I recall some servers where a special bin folder was created in the the user's space and the various commands that need to be run were placed there with permissions for their use.
Hope that helps.