Cache lines even if rate limit expired

The previous check to not search when the rate limit expired was too
eager and cut off before we could even check if we had already cached
the line. Now, the cache will be checked first before we check if we
need to abort because of rate limiting.