Defining entrance and exit criteria is something I have never been comfortable with it always seems to end it a compromise.
It brings you back to that age old question when is your application good enough for release.
The XP approach deals with this fairly well where it states that 100% of all unit and integration tests must pass and a percentage defined by the customer of the functional tests must pass. Ie some compromise must be made between deadline and quality but it is the customer who makes the call.
We should state that all testcases will be executed, and our expectations are that 95% (or whatever we choose) should pass in order to be successfully tested.
The auditor indicated he's been at some companies where the answer was - well - we executed most testcases, but we ran out of time for the others
This is a valid point. One way this could be handled is through your RTM. If your requirements are prioritized and your test cases trace to your requirements then you have a priority assigned to your test cases. Therefore, if you would run out of time you could focus your efforts on all priority 1's.