The problem with that part of the NDA is that Frotz is available on the app store and has been for a month or two. Frotz is an interactive fiction application (arguably interpreted) and also open source (gplv2, http://code.google.com/p/iphonefrotz/), two things technically incompatible with the NDA.

I don't really think Apple meant to include the likes of Frotz. Seems like the biggest issue is arbitrary rejection (as you mention), and not so much whether or not the NDA is strictly followed..exceptions made for applications that Apple sees nothing bad in. Of course, Flash would be a more direct threat to the App Store than IF, sooo...I have a feeling that even if there were some sort of loophole, Apple would reject it anyway. Shame, cause I'm not really interested in games, I just want to view some websites that don't have non-Flash fallback (sometimes for a legitimate reason) on my phone.

This also sucks from a developer perspective, but that particular issue has been discussed to excess everywhere without Apple yet doing something positive..