diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
index 0daec5d..37c81b0 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
@@ -31,6 +31,11 @@
 
   /**
    * Returns the names of all the packages under a given directory.
+   *
+   * <p>Packages returned by this method and passed into
+   * {@link #bulkGetPackages(EventHandler, Iterable)} are expected to return successful
+   * {@link Package} values.
+   *
    * @param directory a {@link RootedPath} specifying the directory to search
    * @param excludedSubdirectories a set of {@link PathFragment}s, all of which are beneath
    *     {@code directory}, specifying transitive subdirectories to exclude
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
index 8c0e56c..5703c42 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
@@ -99,8 +99,9 @@
 
     ImmutableMap.Builder<PackageIdentifier, Package> pkgResults = ImmutableMap.builder();
     Map<SkyKey, SkyValue> packages = graph.getSuccessfulValues(pkgKeys);
-    for (PackageIdentifier pkgId : pkgIds) {
-      PackageValue pkgValue = (PackageValue) packages.get(PackageValue.key(pkgId));
+    for (Map.Entry<SkyKey, SkyValue> pkgEntry : packages.entrySet()) {
+      PackageIdentifier pkgId = (PackageIdentifier) pkgEntry.getKey().argument();
+      PackageValue pkgValue = (PackageValue) pkgEntry.getValue();
       pkgResults.put(pkgId, Preconditions.checkNotNull(pkgValue.getPackage(), pkgId));
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
index 65a737e..46bd0c2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
@@ -20,6 +20,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
@@ -147,6 +148,10 @@
           throws TargetParsingException, InterruptedException {
     try {
       Map<PackageIdentifier, Package> pkgs = bulkGetPackages(pkgIds);
+      if (pkgs.size() != Iterables.size(pkgIds)) {
+        throw new IllegalStateException("Bulk package retrieval missing results: "
+            + Sets.difference(ImmutableSet.copyOf(pkgIds), pkgs.keySet()));
+      }
       ImmutableMap.Builder<PackageIdentifier, ResolvedTargets<Target>> result =
               ImmutableMap.builder();
       for (PackageIdentifier pkgId : pkgIds) {
@@ -157,7 +162,8 @@
     } catch (NoSuchThingException e) {
       String message = TargetPatternResolverUtil.getParsingErrorMessage(
               e.getMessage(), originalPattern);
-      throw new TargetParsingException(message, e);
+      throw new IllegalStateException(
+          "Mismatch: Expected given pkgIds to correspond to valid Packages. " + message, e);
     }
   }