Removing elements from stub cache by Major key only does not always work.

BUG=

Review-Url: https://codereview.chromium.org/2551353003
Cr-Commit-Position: refs/heads/master@{#41544}