他のサイトでも色々紹介されていますので、あまり紹介されていないパターンのご紹介です。
どうしても実行できないときは、まずexecを呼び出しているときのカレントワーキングディレクトリを確認してください。
echo getcwd()."<br/>";
同じPHPのfile_exists関数によるexeの存在チェックや、IIS上で動作するaspなどからは呼び出せても、
execでは別のパスを使用するようです。
PHPソースを別サーバーにおいている場合などでは要注意です。
もし怪しければ、execの実行前に、
chdir('working_dir');
でexecの実行まえにカレントワーキングディレクトリを実行したいexeのあるディレクトリに変更しておきましょう。