そこでスクリプトを以下のように書き換えて実行しました。

clearstatcache(); // ←追加
if(!file_exists('test.txt')) {
　exec('make_test');
　clearstatcache(); // ←追加
　if(file_exists('test.txt')) {
　　echo 'ファイルがある';
　}
　else {
　　echo 'ファイルが無い';
　}
}
else {
　echo 'ファイルがある';
}

でも結果は変わりません。
webで調べてみたところ、
http://ns1.php.gr.jp/php-jp/archives/msg05496.html
のような症状を発見し、これと同様のことが起きているものと思われます。
しかしこのMLは、結論が出ることなく話題が終わっています。

PHPのバージョンは 4.3.7 です。

解決策をご存知の方、ぜひ教えてください。