Resolving MultiStore inconsistencies

A few issues were spotted in MultiStore which needs to be resolved before #2077 (closed) can proceed.

1. *scan_each fallback and block execution behaviour -- gitlab-org/gitlab#386745 (closed)
2. Cache miss behaviour -- gitlab-org/gitlab#386978 (closed)

cc @alejandro (heavy context on MultiStore) and @marcogreg (working on repository cache which is blocked by this)