Index: /trunk/src/VBox/Main/include/MachineImpl.h
===================================================================
--- /trunk/src/VBox/Main/include/MachineImpl.h	(revision 35835)
+++ /trunk/src/VBox/Main/include/MachineImpl.h	(revision 35836)
@@ -782,4 +782,8 @@
     HRESULT saveStateSettings(int aFlags);
 
+    void addMediumToRegistry(ComObjPtr<Medium> &pMedium,
+                             GuidList &llRegistriesThatNeedSaving,
+                             Guid *puuid);
+
     HRESULT createImplicitDiffs(IProgress *aProgress,
                                 ULONG aWeight,
Index: /trunk/src/VBox/Main/include/MediumImpl.h
===================================================================
--- /trunk/src/VBox/Main/include/MediumImpl.h	(revision 35835)
+++ /trunk/src/VBox/Main/include/MediumImpl.h	(revision 35836)
@@ -177,5 +177,5 @@
     bool addRegistry(const Guid& id);
     bool isInRegistry(const Guid& id);
-    const Guid& getFirstRegistryMachineId() const;
+    bool getFirstRegistryMachineId(Guid &uuid) const;
     HRESULT addToRegistryIDList(GuidList &llRegistryIDs);
 
Index: /trunk/src/VBox/Main/src-server/MachineImpl.cpp
===================================================================
--- /trunk/src/VBox/Main/src-server/MachineImpl.cpp	(revision 35835)
+++ /trunk/src/VBox/Main/src-server/MachineImpl.cpp	(revision 35836)
@@ -3624,8 +3624,18 @@
         ComObjPtr<Medium> diff;
         diff.createObject();
+        // store this diff in the same registry as the parent
+        Guid uuidRegistryParent;
+        if (!medium->getFirstRegistryMachineId(uuidRegistryParent))
+        {
+            // parent image has no registry: this can happen if we're attaching a new immutable
+            // image that has not yet been attached (medium then points to the base and we're
+            // creating the diff image for the immutable, and the parent is not yet registered);
+            // put the parent in the machine registry then
+            addMediumToRegistry(medium, llRegistriesThatNeedSaving, &uuidRegistryParent);
+        }
         rc = diff->init(mParent,
                         medium->getPreferredDiffFormat(),
                         strFullSnapshotFolder.append(RTPATH_SLASH_STR),
-                        medium->getFirstRegistryMachineId(),         // store this diff in the same registry as the parent
+                        uuidRegistryParent,
                         &llRegistriesThatNeedSaving);
         if (FAILED(rc)) return rc;
@@ -3702,15 +3712,7 @@
         if (FAILED(rc)) return rc;
 
-        // and decide which medium registry to use now that the medium is attached:
-        Guid uuid;
-        if (mData->pMachineConfigFile->canHaveOwnMediaRegistry())
-            // machine XML is VirtualBox 4.0 or higher:
-            uuid = getId();     // machine UUID
-        else
-            uuid = mParent->getGlobalRegistryId(); // VirtualBox global registry UUID
-
-        if (medium->addRegistry(uuid))
-            // registry actually changed:
-            mParent->addGuidToListUniquely(llRegistriesThatNeedSaving, uuid);
+        addMediumToRegistry(medium,
+                            llRegistriesThatNeedSaving,
+                            NULL /* Guid *puuid */);
     }
 
@@ -3948,15 +3950,5 @@
             pMedium->addBackReference(mData->mUuid);
 
-            // and decide which medium registry to use now that the medium is attached:
-            Guid uuid;
-            if (mData->pMachineConfigFile->canHaveOwnMediaRegistry())
-                // machine XML is VirtualBox 4.0 or higher:
-                uuid = getId();     // machine UUID
-            else
-                uuid = mParent->getGlobalRegistryId(); // VirtualBox global registry UUID
-
-            if (pMedium->addRegistry(uuid))
-                // registry actually changed:
-                mParent->addGuidToListUniquely(llRegistriesThatNeedSaving, uuid);
+            addMediumToRegistry(pMedium, llRegistriesThatNeedSaving, NULL /* Guid *puuid */ );
         }
 
@@ -8739,4 +8731,38 @@
 
 /**
+ * Ensures that the given medium is added to a media registry. If this machine
+ * was created with 4.0 or later, then the machine registry is used. Otherwise
+ * the global VirtualBox media registry is used. If the medium was actually
+ * added to a registry (because it wasn't in the registry yet), the UUID of
+ * that registry is added to the given list so that the caller can save the
+ * registry.
+ *
+ * Caller must hold machine read lock!
+ *
+ * @param pMedium
+ * @param llRegistriesThatNeedSaving
+ * @param puuid Optional buffer that receives the registry UUID that was used.
+ */
+void Machine::addMediumToRegistry(ComObjPtr<Medium> &pMedium,
+                                  GuidList &llRegistriesThatNeedSaving,
+                                  Guid *puuid)
+{
+    // decide which medium registry to use now that the medium is attached:
+    Guid uuid;
+    if (mData->pMachineConfigFile->canHaveOwnMediaRegistry())
+        // machine XML is VirtualBox 4.0 or higher:
+        uuid = getId();     // machine UUID
+    else
+        uuid = mParent->getGlobalRegistryId(); // VirtualBox global registry UUID
+
+    if (pMedium->addRegistry(uuid))
+        // registry actually changed:
+        mParent->addGuidToListUniquely(llRegistriesThatNeedSaving, uuid);
+
+    if (puuid)
+        *puuid = uuid;
+}
+
+/**
  * Creates differencing hard disks for all normal hard disks attached to this
  * machine and a new set of attachments to refer to created disks.
@@ -8894,8 +8920,13 @@
             ComObjPtr<Medium> diff;
             diff.createObject();
+            // store the diff in the same registry as the parent
+            // (this cannot fail here because we can't create implicit diffs for
+            // unregistered images)
+            Guid uuidRegistryParent;
+            Assert(pMedium->getFirstRegistryMachineId(uuidRegistryParent));
             rc = diff->init(mParent,
                             pMedium->getPreferredDiffFormat(),
                             strFullSnapshotFolder.append(RTPATH_SLASH_STR),
-                            pMedium->getFirstRegistryMachineId(),        // store the diff in the same registry as the parent
+                            uuidRegistryParent,
                             pllRegistriesThatNeedSaving);
             if (FAILED(rc)) throw rc;
Index: /trunk/src/VBox/Main/src-server/MediumImpl.cpp
===================================================================
--- /trunk/src/VBox/Main/src-server/MediumImpl.cpp	(revision 35835)
+++ /trunk/src/VBox/Main/src-server/MediumImpl.cpp	(revision 35836)
@@ -3131,6 +3131,6 @@
  * machine XML this medium is listed).
  *
- * Every medium must now (4.0) reside in at least one media registry, which is identified by
- * a UUID. This is either a machine UUID if the machine is from 4.0 or newer, in which case
+ * Every attached medium must now (4.0) reside in at least one media registry, which is identified
+ * by a UUID. This is either a machine UUID if the machine is from 4.0 or newer, in which case
  * machines have their own media registries, or it is the pseudo-UUID of the VirtualBox
  * object if the machine is old and still needs the global registry in VirtualBox.xml.
@@ -3141,4 +3141,7 @@
  * case, only VM2's registry is used for the disk in question.)
  *
+ * If there is no medium registry, particularly if the medium has not been attached yet, this
+ * does not modify uuid and returns false.
+ *
  * ISOs and RAWs, by contrast, can be in more than one repository to make things easier for
  * the user.
@@ -3146,9 +3149,15 @@
  * Must have caller + locking!
  *
- * @return
- */
-const Guid& Medium::getFirstRegistryMachineId() const
-{
-    return m->llRegistryIDs.front();
+ * @param uuid Receives first registry machine UUID, if available.
+ * @return true if uuid was set.
+ */
+bool Medium::getFirstRegistryMachineId(Guid &uuid) const
+{
+    if (m->llRegistryIDs.size())
+    {
+        uuid = m->llRegistryIDs.front();
+        return true;
+    }
+    return false;
 }
 
