たぶんfindの処理が再帰的になってしまわないようにとかそういう理由で、 findが呼び出された時点でのディレクトリツリーのリストをfind自身が持ってるんだと思うよ。 んでfindがディレクトリの中身を処理しようとしたときに、既に親ディレクトリがrm -rfされているから find が No such file or directoryと言うんじゃないかな。
>>589とはちょっと違うような気がしてきたよ。 findはマッチするエントリがあったら子プロセスを作って-exec {}を実行、帰ってきたら探索を続けるっぽいよ。 ディレクトリにマッチしていた場合はfchdirするためにopenするんだけど、 その時にはもうディレクトリが消されているからNo such file or directoryだよ。