I have also noticed this arbitrarity when it comes to including a native executable in the extension package. Some extensions do include executables, while at the same time the guidelines suggest that you should not do so.
I read once in the comments of some Chrome bug report how two Google engineers were discussing about the advantages of including the executable in the package. One of them mentioned that by allowing the executable in the package, they could take advantage of the CWS automated virus and security checks for scanning the executable too.
Given the fact that there actually are packages with .exe files inside, I would say that the CWS team is not clear about whether to allow or disallow this practice.
@Tony BenBrahim, the notice you got saying "Packaged and Hosted apps should not Require a local executable, other than the Chrome runtime, to run".
That notice is clearly bogus. Policies for Apps do not apply to extensions and vice versa.
Apps are not even allowed in the webstore anymore, so it doesn't make sense that they are trying to enforce those policies.