According to the xargs documentation, the xargs utility is supposed to return status 126 or 127 if the command canot be run.   However, xarsg returns 126 if the utility returns 126, and 127 if the utility returns 127. 

That means that when xargs returns 126, you can't be sure whether it's because the utility could not be run, or that it could be run but it returned 126.

This problem is addressed by the code changes included in Leslie Polzer's Summer of Code work, but this has not yet been merged.