Add negative caching tests and fixes. (#7361)

This adds test coverage for the negative caching feature and makes some
fixes as a result of the test's findings.

(cherry picked from commit 8eb68266167d8f8b3fa3a00ca9f6b7889e8ec101)
15 files changed