--- a/mailnews/addrbook/public/nsIAbCard.idl
+++ b/mailnews/addrbook/public/nsIAbCard.idl
@@ -48,17 +48,25 @@ interface nsIAbPreferMailFormat {
     const unsigned long unknown   = 0;
     const unsigned long plaintext = 1;
     const unsigned long html      = 2;
 };
 
 /**
  * An interface representing an address book card.
  *
- * Fundamentally, it is a collection of properties. Modifying a property in
+ * The UUID of a card is a composition of a directory ID and a per-directory ID.
+ * The per-directory ID is reflected in the localId property. If either of these
+ * properties change, the UUID will change correspondingly.
+ *
+ * None of these IDs will be reflected in the property collection. Neither
+ * nsIAbCard::properties, nsIAbCard::deleteProperty, nor any of the property
+ * getters and setters are able to interact with these properties.
+ *
+ * Fundamentally, a card is a collection of properties. Modifying a property in
  * some way on a card does not change the backend used to store the card; the
  * directory is required to do make the changes here.
  *
  * The following are the core properties that are used:
  * - Names:
  *   - FirstName, LastName
  *   - PhoneticFirstName, PhoneticLastName
  *   - DisplayName, NickName
@@ -85,20 +93,65 @@ interface nsIAbPreferMailFormat {
  *   - PopularityIndex
  *   - PreferMailFormat (see nsIAbPreferMailFormat)
  * - Boolean properties:
  *   - AllowRemoteContent
  * - Photo properties:
  *   - PhotoName
  *   - PhotoType
  *   - PhotoURI
+ *
+ * The contract id for the standard implementation is
+ * <tt>\@mozilla.org/addressbook/cardproperty;1</tt>.
  */
-[scriptable, uuid(fdac4023-cd19-4e75-9a88-8e48881076ea)]
+[scriptable, uuid(21c4308b-e1e2-4ab2-abdc-e1f4431c7055)]
 interface nsIAbCard : nsIAbItem {
   /**
+   * The UUID for the nsIAbDirectory containing this card.
+   *
+   * The directory considered to contain this card is the directory which
+   * produced this card (e.g., through nsIAbDirectory::getCardForProperty) or
+   * the last directory to modify this card, if another directory did so. If the
+   * last directory to modify this card deleted it, then this card is considered
+   * unassociated.
+   *
+   * If this card is not associated with a directory, this string will be empty.
+   *
+   * There is no standardized way to associate a card with multiple directories.
+   *
+   * Consumers of this interface outside of directory implementations SHOULD
+   * NOT, in general, modify this property.
+   */
+  attribute AUTF8String directoryId;
+
+  /**
+   * The per-directory ID of this card.
+   *
+   * This property is the second part of the tuple logically representing a card
+   * UUID. It shares many requirements with that of nsIAbItem::uuid. In
+   * particular:
+   * - It MUST be unique (within the scope of its directory).
+   * - The empty string MUST only be used to indicate that it has not yet been
+   *   assigned a localId.
+   * - It is STRONGLY RECOMMENDED that this id is consistent across sessions and
+   *   that, should the card be deleted, its ids will not be reused.
+   * - The format of localId is left undefined.
+   *
+   * As long as directoryId is not changed, this property SHOULD NOT be changed.
+   * If directoryId is changed, the new directory MAY choose to reuse the same
+   * localId if reasonable. However, consumers MUST NOT assume that two cards
+   * with different directoryIds but the same localId are logically the same
+   * card.
+   *
+   * Similar to directoryId, consumers of cards outside of directory
+   * implementations SHOULD NOT, in general, modify this property.
+   */
+  attribute AUTF8String localId;
+
+  /**
    * A list of all the properties that this card has as an enumerator, whose
    * members are all nsIProperty objects.
    */
   readonly attribute nsISimpleEnumerator properties;
 
   /**
    * Returns a property for the given name.
    *

--- a/mailnews/addrbook/public/nsIAbDirectory.idl
+++ b/mailnews/addrbook/public/nsIAbDirectory.idl
@@ -55,16 +55,22 @@ interface nsIMutableArray;
 #define kCollectedAddressbook      "history.mab"
 #define kCollectedAddressbookUri   "moz-abmdbdirectory://history.mab"
 
 #define kABFileName_PreviousSuffix ".na2" /* final v2 address book format */
 #define kABFileName_PreviousSuffixLen 4
 #define kABFileName_CurrentSuffix ".mab"  /* v3 address book extension */
 %}
 
+/**
+ * A top-level address book directory.
+ *
+ * The UUID of an nsIAbDirectory is its preference ID and its name, concatenated
+ * together.
+ */
 [scriptable, uuid(0ef8d12d-f553-4a28-85b5-c838aff34ab1)]
 interface nsIAbDirectory : nsIAbCollection {
 
   /**
    * The chrome URI to use for bringing up a dialog to edit this directory.
    * When opening the dialog, use a JS argument of
    * {selectedDirectory: thisdir} where thisdir is this directory that you just
    * got the chrome URI from.

--- a/mailnews/addrbook/public/nsIAbItem.idl
+++ b/mailnews/addrbook/public/nsIAbItem.idl
@@ -40,19 +40,36 @@
 #include "nsISupports.idl"
 
 interface nsIMsgHeaderParser;
 interface nsIStringBundle;
 
 /**
  * A containable item for address books.
  */
-[scriptable, uuid(f7320616-3139-419b-a7c3-37441da3caf3)]
+[scriptable, uuid(bb691a55-cbfe-4cf8-974a-e18cfa845a73)]
 interface nsIAbItem : nsISupports {
   /**
+   * A universally-unique identifier for this item.
+   *
+   * If this item cannot be associated with a UUID for some reason, it MUST
+   * return the empty string. The empty string MUST NOT be a valid UUID for any
+   * item. Under no circumstances may this function throw an error.
+   *
+   * It is STRONGLY RECOMMENDED that implementations guarantee that this UUID
+   * will not change between two different sessions of the application and that,
+   * if this item is deleted, the UUID will not be reused.
+   *
+   * The format of the UUID for a generic nsIAbItem is purposefully left
+   * undefined, although any item contained by an nsIAbDirectory SHOULD use
+   * nsIAbManager::generateUUID to generate the UUID.
+   */
+  readonly attribute AUTF8String uuid;
+
+  /**
    * @{
    * These constants reflect the possible values of the
    * mail.addr_book.lastnamefirst preferences. They are intended to be used in
    * generateName, defined below.
    */
    const unsigned long GENERATE_DISPLAY_NAME = 0;
    const unsigned long GENERATE_LAST_FIRST_ORDER = 1;
    const unsigned long GENERATE_FIRST_LAST_ORDER = 2;

--- a/mailnews/addrbook/public/nsIAbManager.idl
+++ b/mailnews/addrbook/public/nsIAbManager.idl
@@ -48,17 +48,17 @@ interface nsISimpleEnumerator;
 
 /**
  * nsIAbManager is an interface to the main address book mananger
  * via the contract id "@mozilla.org/abmanager;1"
  *
  * It contains the main functions to create and delete address books as well
  * as some helper functions.
  */
-[scriptable, uuid(3b869b86-c4df-4cae-8dc9-c18073d2593f)]
+[scriptable, uuid(549bf1f6-ada4-40c5-9f59-4ea9eda4a935)]
 interface nsIAbManager : nsISupports 
 {
   /**
    * Returns an enumerator containing all the top-level directories
    * (non-recursive)
    */
   readonly attribute nsISimpleEnumerator directories;
 
@@ -184,9 +184,21 @@ interface nsIAbManager : nsISupports
   /**
    * Translates an escaped vcard string into a nsIAbCard.
    *
    * @param  escapedVCardStr  The string containing the vcard.
    *
    * @return            A card containing the translated vcard data.
    */
   nsIAbCard escapedVCardToAbCard(in string escapedVCardStr);
+
+  /**
+   * Generates a UUID from a (directory ID, local ID) tuple.
+   *
+   * Use of this method is preferred in such cases, since it is designed to work
+   * with other methods of this interface.
+   *
+   * @param directoryId The directory ID.
+   * @param localId     The per-directory ID.
+   * @return            A string to use for the UUID.
+   */
+  AUTF8String generateUUID(in AUTF8String directoryId, in AUTF8String localId);
 };

--- a/mailnews/addrbook/src/nsAbCardProperty.cpp
+++ b/mailnews/addrbook/src/nsAbCardProperty.cpp
@@ -53,16 +53,17 @@
 #include "nsINetUtil.h"
 #include "nsComponentManagerUtils.h"
 #include "nsServiceManagerUtils.h"
 #include "nsMemory.h"
 #include "nsVCardObj.h"
 #include "nsIMutableArray.h"
 #include "nsArrayUtils.h"
 #include "mozITXTToHTMLConv.h"
+#include "nsIAbManager.h"
 
 #include "nsIProperty.h"
 #include "nsCOMArray.h"
 #include "nsArrayEnumerator.h"
 #include "prmem.h"
 
 #define PREF_MAIL_ADDR_BOOK_LASTNAMEFIRST "mail.addr_book.lastnamefirst"
 
@@ -135,17 +136,57 @@ nsAbCardProperty::nsAbCardProperty()
   SetPropertyAsUint32(kLastModifiedDateProperty, 0);
   SetPropertyAsBool(kAllowRemoteContentProperty, PR_FALSE);
 }
 
 nsAbCardProperty::~nsAbCardProperty(void)
 {
 }
 
-NS_IMPL_ISUPPORTS1(nsAbCardProperty, nsIAbCard)
+NS_IMPL_ISUPPORTS2(nsAbCardProperty, nsIAbCard, nsIAbItem)
+
+NS_IMETHODIMP nsAbCardProperty::GetUuid(nsACString &uuid)
+{
+  // If we have indeterminate sub-ids, return an empty uuid.
+  if (m_directoryId.Equals("") || m_localId.Equals(""))
+  {
+    uuid.Truncate();
+    return NS_OK;
+  }
+
+  nsresult rv;
+  nsCOMPtr<nsIAbManager> manager = do_GetService(NS_ABMANAGER_CONTRACTID, &rv);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return manager->GenerateUUID(m_directoryId, m_localId, uuid);
+}
+
+NS_IMETHODIMP nsAbCardProperty::GetDirectoryId(nsACString &dirId)
+{
+  dirId = m_directoryId;
+  return NS_OK;
+}
+
+NS_IMETHODIMP nsAbCardProperty::SetDirectoryId(const nsACString &aDirId)
+{
+  m_directoryId = aDirId;
+  return NS_OK;
+}
+
+NS_IMETHODIMP nsAbCardProperty::GetLocalId(nsACString &localId)
+{
+  localId = m_localId;
+  return NS_OK;
+}
+
+NS_IMETHODIMP nsAbCardProperty::SetLocalId(const nsACString &aLocalId)
+{
+  m_localId = aLocalId;
+  return NS_OK;
+}
 
 ////////////////////////////////////////////////////////////////////////////////
 
 NS_IMETHODIMP nsAbCardProperty::GetIsMailList(PRBool *aIsMailList)
 {
     *aIsMailList = m_IsMailList;
     return NS_OK;
 }

--- a/mailnews/addrbook/src/nsAbCardProperty.h
+++ b/mailnews/addrbook/src/nsAbCardProperty.h
@@ -72,16 +72,17 @@ public:
 
 protected:
 	PRBool   m_IsMailList;
 	nsCString m_MailListURI;
 
   // Store most of the properties here
   nsInterfaceHashtable<nsCStringHashKey, nsIVariant> m_properties;
 
+  nsCString m_directoryId, m_localId;
 private:
   nsresult AppendSection(const AppendItem *aArray, PRInt16 aCount, const nsString& aHeading, nsIStringBundle *aBundle, mozITXTToHTMLConv *aConv, nsString &aResult);
   nsresult AppendLine(const AppendItem &aItem, mozITXTToHTMLConv *aConv, nsString &aResult);
   nsresult AppendLabel(const AppendItem &aItem, nsIStringBundle *aBundle, mozITXTToHTMLConv *aConv, nsString &aResult);
   nsresult AppendCityStateZip(const AppendItem &aItem, nsIStringBundle *aBundle, mozITXTToHTMLConv *aConv, nsString &aResult);
 
   nsresult ConvertToBase64EncodedXML(nsACString &result);
   nsresult ConvertToXMLPrintData(nsAString &result);

--- a/mailnews/addrbook/src/nsAbDirProperty.cpp
+++ b/mailnews/addrbook/src/nsAbDirProperty.cpp
@@ -70,17 +70,29 @@ nsAbDirProperty::~nsAbDirProperty(void)
     NS_ASSERTION(NS_SUCCEEDED(rv), "Count failed");
     PRInt32 i;
     for (i = count - 1; i >= 0; i--)
       m_AddressList->RemoveElementAt(i);
   }
 #endif
 }
 
-NS_IMPL_ISUPPORTS1(nsAbDirProperty,nsIAbDirectory)
+NS_IMPL_ISUPPORTS3(nsAbDirProperty, nsIAbDirectory, nsIAbCollection, nsIAbItem)
+
+NS_IMETHODIMP nsAbDirProperty::GetUuid(nsACString &uuid)
+{
+  // XXX: not all directories have a dirPrefId...
+  nsresult rv = GetDirPrefId(uuid);
+  NS_ENSURE_SUCCESS(rv, rv);
+  uuid.Append('&');
+  nsString dirName;
+  GetDirName(dirName);
+  uuid.Append(NS_ConvertUTF16toUTF8(dirName));
+  return rv;
+}
 
 NS_IMETHODIMP nsAbDirProperty::GenerateName(PRInt32 aGenerateFormat,
                                             nsIStringBundle *aBundle,
                                             nsAString &name)
 {
   return GetDirName(name);
 }
 

--- a/mailnews/addrbook/src/nsAbLDAPCard.cpp
+++ b/mailnews/addrbook/src/nsAbLDAPCard.cpp
@@ -270,16 +270,17 @@ NS_IMETHODIMP nsAbLDAPCard::BuildRdn(nsI
 
 NS_IMETHODIMP nsAbLDAPCard::GetDn(nsACString &aDN)
 {
   return GetPropertyAsAUTF8String(kDNColumn, aDN);
 }
 
 NS_IMETHODIMP nsAbLDAPCard::SetDn(const nsACString &aDN)
 {
+  SetLocalId(aDN);
   return SetPropertyAsAUTF8String(kDNColumn, aDN);
 }
 
 NS_IMETHODIMP nsAbLDAPCard::SetMetaProperties(nsILDAPMessage *aMessage)
 {
   NS_ENSURE_ARG_POINTER(aMessage);
   
   // Get DN

--- a/mailnews/addrbook/src/nsAbLDAPDirectory.cpp
+++ b/mailnews/addrbook/src/nsAbLDAPDirectory.cpp
@@ -804,16 +804,20 @@ NS_IMETHODIMP nsAbLDAPDirectory::AddCard
     cardDN);
   NS_ENSURE_SUCCESS(rv, rv);
   cardDN.AppendLiteral(",");
   cardDN.Append(baseDN);
 
   rv = card->SetDn(cardDN);
   NS_ENSURE_SUCCESS(rv, rv);
 
+  nsCAutoString ourUuid;
+  GetUuid(ourUuid);
+  copyToCard->SetDirectoryId(ourUuid);
+
   // Launch query
   rv = DoModify(this, nsILDAPModification::MOD_ADD, cardDN, modArray,
                 EmptyCString(), EmptyCString());
   NS_ENSURE_SUCCESS(rv, rv);
 
   NS_ADDREF(*aAddedCard = copyToCard);
   return NS_OK;
 }
@@ -837,16 +841,19 @@ NS_IMETHODIMP nsAbLDAPDirectory::DeleteC
     }
 
     // Set up the search ldap url - this is mURL
     rv = Initiate();
     NS_ENSURE_SUCCESS(rv, rv);
     
     rv = card->GetDn(cardDN);
     NS_ENSURE_SUCCESS(rv, rv);
+
+    nsCOMPtr<nsIAbCard> realCard(do_QueryInterface(card));
+    realCard->SetDirectoryId(EmptyCString());
    
     // Launch query
     rv = DoModify(this, nsILDAPModification::MOD_DELETE, cardDN, nsnull,
                   EmptyCString(), EmptyCString());
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   return NS_OK;

--- a/mailnews/addrbook/src/nsAbLDAPDirectoryQuery.cpp
+++ b/mailnews/addrbook/src/nsAbLDAPDirectoryQuery.cpp
@@ -397,16 +397,17 @@ NS_IMETHODIMP nsAbLDAPDirectoryQuery::Do
   // If connection params have changed re-create connection
   // else reuse existing connection
   
   PRBool redoConnection = PR_FALSE;
   
   if (!mConnection || !mDirectoryUrl)
   {
     mDirectoryUrl = currentUrl;
+    aDirectory->GetUuid(mDirectoryId);
     mCurrentLogin = login;
     mCurrentMechanism = saslMechanism;
     mCurrentProtocolVersion = protocolVersion;
     redoConnection = PR_TRUE;
   }
   else
   {
     PRBool equal;
@@ -415,16 +416,17 @@ NS_IMETHODIMP nsAbLDAPDirectoryQuery::Do
   
     nsCString spec;
     mDirectoryUrl->GetSpec(spec);
     currentUrl->GetSpec(spec);
 
     if (!equal)
     {
       mDirectoryUrl = currentUrl;
+      aDirectory->GetUuid(mDirectoryId);
       mCurrentLogin = login;
       mCurrentMechanism = saslMechanism;
       mCurrentProtocolVersion = protocolVersion;
       redoConnection = PR_TRUE;
     }
     else
     {
       // Has login or version changed?
@@ -623,16 +625,18 @@ NS_IMETHODIMP nsAbLDAPDirectoryQuery::St
   if (listener)
     return listener->Cancel();
 
   return NS_OK;
 }
 
 NS_IMETHODIMP nsAbLDAPDirectoryQuery::OnQueryFoundCard(nsIAbCard *aCard)
 {
+  aCard->SetDirectoryId(mDirectoryId);
+
   for (PRInt32 i = 0; i < mListeners.Count(); ++i)
     mListeners[i]->OnSearchFoundCard(aCard);
 
   return NS_OK;
 }
 
 NS_IMETHODIMP nsAbLDAPDirectoryQuery::OnQueryResult(PRInt32 aResult,
                                                     PRInt32 aErrorCode)

--- a/mailnews/addrbook/src/nsAbLDAPDirectoryQuery.h
+++ b/mailnews/addrbook/src/nsAbLDAPDirectoryQuery.h
@@ -61,16 +61,17 @@ public:
   virtual ~nsAbLDAPDirectoryQuery();
 
 protected:
   nsCOMPtr<nsILDAPMessageListener> mListener;
 
 private:
   nsCOMPtr<nsILDAPConnection> mConnection;
   nsCOMPtr<nsILDAPURL> mDirectoryUrl;
+  nsCString mDirectoryId;
   nsCOMArray<nsIAbDirSearchListener> mListeners;
   nsCString mCurrentLogin;
   nsCString mCurrentMechanism;
   PRUint32 mCurrentProtocolVersion;
 
   PRBool mInitialized;
 };
 

--- a/mailnews/addrbook/src/nsAbManager.cpp
+++ b/mailnews/addrbook/src/nsAbManager.cpp
@@ -1240,8 +1240,18 @@ nsAbManager::Handle(nsICommandLine* aCmd
 }
 
 NS_IMETHODIMP
 nsAbManager::GetHelpInfo(nsACString& aResult)
 {
   aResult.Assign(NS_LITERAL_CSTRING("  -addressbook       Open the address book at startup.\n"));
   return NS_OK;
 }
+
+NS_IMETHODIMP
+nsAbManager::GenerateUUID(const nsACString &aDirectoryId,
+                          const nsACString &aLocalId, nsACString &uuid)
+{
+  uuid.Assign(aDirectoryId);
+  uuid.Append('#');
+  uuid.Append(aLocalId);
+  return NS_OK;
+}

--- a/mailnews/addrbook/src/nsAbOSXCard.mm
+++ b/mailnews/addrbook/src/nsAbOSXCard.mm
@@ -182,16 +182,18 @@ nsAbOSXCard::Init(const char *aUri)
 {
   if (strncmp(aUri, NS_ABOSXCARD_URI_PREFIX,
               sizeof(NS_ABOSXCARD_URI_PREFIX) - 1) != 0)
     return NS_ERROR_FAILURE;
   
   nsresult rv = nsRDFResource::Init(aUri);
   NS_ENSURE_SUCCESS(rv, rv);
   
+  SetLocalId(nsDependentCString(aUri));
+
   return Update(PR_FALSE);
 }
 
 nsresult
 nsAbOSXCard::Update(PRBool aNotify)
 {
   ABAddressBook *addressBook = [ABAddressBook sharedAddressBook];
 

--- a/mailnews/addrbook/src/nsAbOSXDirectory.mm
+++ b/mailnews/addrbook/src/nsAbOSXDirectory.mm
@@ -492,24 +492,29 @@ nsAbOSXDirectory::Init(const char *aUri)
       mCardList = do_CreateInstance(NS_ARRAY_CONTRACTID, &rv);
     else
       rv = mCardList->Clear();
     NS_ENSURE_SUCCESS(rv, rv);
 
     cardList = mCardList;
   }
 
+  nsCAutoString ourUuid;
+  GetUuid(ourUuid);
+
   unsigned int nbCards = [cards count];
   nsCOMPtr<nsIAbCard> card;
   for (unsigned int i = 0; i < nbCards; ++i)
   {
     rv = ConvertToCard(gRDFService, [cards objectAtIndex:i],
                        getter_AddRefs(card));
     NS_ENSURE_SUCCESS(rv, rv);
 
+    card->SetDirectoryId(ourUuid);
+
     cardList->AppendElement(card, PR_FALSE);
   }
 
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsAbOSXDirectory::GetURI(nsACString &aURI)
@@ -740,16 +745,20 @@ nsAbOSXDirectory::AssertDirectory(nsIAbM
 
   return aManager->NotifyDirectoryItemAdded(this, aDirectory);
 }
 
 nsresult
 nsAbOSXDirectory::AssertCard(nsIAbManager *aManager,
                              nsIAbCard *aCard)
 {
+  nsCAutoString ourUuid;
+  GetUuid(ourUuid);
+  aCard->SetDirectoryId(ourUuid);
+
   nsresult rv = m_IsMailList ? m_AddressList->AppendElement(aCard, PR_FALSE) :
                                mCardList->AppendElement(aCard, PR_FALSE);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return aManager->NotifyDirectoryItemAdded(this, aCard);
 }
 
 nsresult
@@ -813,26 +822,31 @@ nsAbOSXDirectory::GetChildCards(nsISimpl
       return FallbackSearch(expression, aCards);
 
     if (!mCardList)
       mCardList = do_CreateInstance(NS_ARRAY_CONTRACTID, &rv);
     else
       mCardList->Clear();
     NS_ENSURE_SUCCESS(rv, rv);
   
+    // The uuid for initializing cards
+    nsCAutoString ourUuid;
+    GetUuid(ourUuid);
+
     // Fill the results array and update the card list
     unsigned int nbCards = [cards count];
   
     unsigned int i;
     nsCOMPtr<nsIAbCard> card;
     for (i = 0; i < nbCards; ++i)
     {
       rv = ConvertToCard(gRDFService, [cards objectAtIndex:i],
                          getter_AddRefs(card));
       NS_ENSURE_SUCCESS(rv, rv);
+      card->SetDirectoryId(ourUuid);
 
       mCardList->AppendElement(card, PR_FALSE);
     }
 
     return NS_NewArrayEnumerator(aCards, mCardList);
   }
 
   // Not a search, so just return the appropriate list of items.
@@ -1040,16 +1054,20 @@ nsAbOSXDirectory::OnSearchFoundCard(nsIA
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   rv = m_AddressList->AppendElement(aCard, PR_FALSE);
   NS_ENSURE_SUCCESS(rv, rv);
   
   rv = mCardList->AppendElement(aCard, PR_FALSE);
   NS_ENSURE_SUCCESS(rv, rv);
+
+  nsCAutoString ourUuid;
+  GetUuid(ourUuid);
+  aCard->SetDirectoryId(ourUuid);
   
   return NS_OK;
 }
 
 nsresult
 nsAbOSXDirectory::FallbackSearch(nsIAbBooleanExpression *aExpression,
                                  nsISimpleEnumerator **aCards)
 {

--- a/mailnews/addrbook/src/nsAbOutlookDirectory.cpp
+++ b/mailnews/addrbook/src/nsAbOutlookDirectory.cpp
@@ -337,16 +337,17 @@ NS_IMETHODIMP nsAbOutlookDirectory::Dele
     nsMapiEntry cardEntry ;
 
     for (i = 0 ; i < nbCards ; ++ i) {
         nsCOMPtr<nsIAbCard> card(do_QueryElementAt(aCardList, i, &retCode));
         NS_ENSURE_SUCCESS(retCode, retCode);
 
         retCode = ExtractCardEntry(card, entryString) ;
         if (NS_SUCCEEDED(retCode) && !entryString.IsEmpty()) {
+            card->SetDirectoryId(EmptyCString());
 
             cardEntry.Assign(entryString) ;
             if (!mapiAddBook->DeleteEntry(*mMapiData, cardEntry)) {
                 PRINTF(("Cannot delete card %s.\n", entryString.get())) ;
             }
             else {
                 mCardList.Remove(card);
                 if (m_IsMailList && m_AddressList) 
@@ -1062,28 +1063,32 @@ nsresult nsAbOutlookDirectory::GetChildC
   nsMapiEntryArray cardEntries;
   LPSRestriction restriction = (LPSRestriction) aRestriction;
 
   if (!mapiAddBook->GetCards(*mMapiData, restriction, cardEntries)) {
     PRINTF(("Cannot get cards.\n"));
     return NS_ERROR_FAILURE;
   }
 
+  nsCAutoString ourUuid;
+  GetUuid(ourUuid);
+
   nsCAutoString entryId;
   nsCAutoString uriName;
   nsCOMPtr<nsIAbCard> childCard;
   nsresult rv;
 
   for (ULONG card = 0; card < cardEntries.mNbEntries; ++card) {
     cardEntries.mEntries[card].ToString(entryId);
     buildAbWinUri(kOutlookCardScheme, mAbWinType, uriName);
     uriName.Append(entryId);
 
     rv = OutlookCardForURI(uriName, getter_AddRefs(childCard));
     NS_ENSURE_SUCCESS(rv, rv);
+    childCard->SetDirectoryId(ourUuid);
 
     aCards->AppendElement(childCard, PR_FALSE);
   }
   return rv;
 }
 
 nsresult nsAbOutlookDirectory::GetChildNodes(nsIMutableArray* aNodes)
 {
@@ -1269,16 +1274,20 @@ nsresult nsAbOutlookDirectory::CreateCar
 
     buildAbWinUri(kOutlookCardScheme, mAbWinType, uri) ;
     uri.Append(entryString) ;
     
     nsCOMPtr<nsIAbCard> newCard;
     retCode = OutlookCardForURI(uri, getter_AddRefs(newCard));
     NS_ENSURE_SUCCESS(retCode, retCode);
 
+    nsCAutoString ourUuid;
+    GetUuid(ourUuid);
+    newCard->SetDirectoryId(ourUuid);
+
     if (!didCopy) {
         retCode = newCard->Copy(aData) ;
         NS_ENSURE_SUCCESS(retCode, retCode) ;
         retCode = ModifyCard(newCard) ;
         NS_ENSURE_SUCCESS(retCode, retCode) ;
     }
     *aNewCard = newCard ;
     NS_ADDREF(*aNewCard) ;
@@ -1485,16 +1494,17 @@ nsresult OutlookCardForURI(const nsACStr
   if (!mapiAddBook->IsOK())
     return NS_ERROR_FAILURE;
 
   nsresult rv;
   nsCOMPtr<nsIAbCard> card = do_CreateInstance(NS_ABCARDPROPERTY_CONTRACTID, &rv);
   NS_ENSURE_SUCCESS(rv, rv);
 
   card->SetPropertyAsAUTF8String("OutlookEntryURI", aUri);
+  card->SetLocalId(aUri);
 
   nsMapiEntry mapiData;
   mapiData.Assign(entry);
 
   nsStringArray unichars;
   if (mapiAddBook->GetPropertiesUString(mapiData, OutlookCardMAPIProps,
                                         index_LastProp, unichars))
   {

--- a/mailnews/addrbook/src/nsAddrDatabase.cpp
+++ b/mailnews/addrbook/src/nsAddrDatabase.cpp
@@ -1247,30 +1247,73 @@ nsresult nsAddrDatabase::AddAttributeCol
 
   return NS_OK;
 }
 
 NS_IMETHODIMP nsAddrDatabase::CreateNewCardAndAddToDB(nsIAbCard *aNewCard, PRBool aNotify /* = FALSE */, nsIAbDirectory *aParent)
 {
   nsCOMPtr <nsIMdbRow> cardRow;
 
-  if (!aNewCard || !m_mdbPabTable || !m_mdbEnv)
+  if (!aNewCard || !m_mdbPabTable || !m_mdbEnv || !m_mdbStore)
     return NS_ERROR_NULL_POINTER;
 
-  nsresult rv = GetNewRow(getter_AddRefs(cardRow));
+  // Per the UUID requirements, we want to try to reuse the local id if at all
+  // possible. nsACString::ToInteger probably won't fail if the local id looks
+  // like "23bozo" (returning 23 instead), but it's okay since we aren't going
+  // to overwrite anything with 23 if it already exists and the id for the row
+  // doesn't matter otherwise.
+  nsresult rv;
+
+  nsCAutoString id;
+  aNewCard->GetLocalId(id);
+
+  mdbOid rowId;
+  rowId.mOid_Scope = m_CardRowScopeToken;
+  rowId.mOid_Id = id.ToInteger(&rv, 10);
+  if (NS_SUCCEEDED(rv))
+  {
+    // Mork is being very naughty here. If the table does not have the oid, we
+    // should be able to reuse it. To be on the safe side, however, we're going
+    // to reference the store's reference count.
+    mdb_count rowCount = 1;
+    m_mdbStore->GetRowRefCount(m_mdbEnv, &rowId, &rowCount);
+    if (rowCount == 0)
+    {
+      // So apparently, the row can have a count of 0 yet still exist (probably
+      // meaning we haven't flushed it out of memory). In this case, we need to
+      // get the row and cut its cells.
+      rv = m_mdbStore->GetRow(m_mdbEnv, &rowId, getter_AddRefs(cardRow));
+      if (NS_SUCCEEDED(rv) && cardRow)
+        cardRow->CutAllColumns(m_mdbEnv);
+      else
+        rv = m_mdbStore->NewRowWithOid(m_mdbEnv, &rowId, getter_AddRefs(cardRow));
+    }
+  }
+
+  // If we don't have a cardRow yet, just get one with any ol' id.
+  if (!cardRow)
+    rv = GetNewRow(getter_AddRefs(cardRow));
+
   if (NS_SUCCEEDED(rv) && cardRow)
   {
     AddAttributeColumnsToRow(aNewCard, cardRow);
     AddRecordKeyColumnToRow(cardRow);
 
     // we need to do this for dnd
     PRUint32 key = 0;
     rv = GetIntColumn(cardRow, m_RecordKeyColumnToken, &key, 0);
     if (NS_SUCCEEDED(rv))
       aNewCard->SetPropertyAsUint32(kRecordKeyColumn, key);
+    
+    aNewCard->GetPropertyAsAUTF8String(kRowIDProperty, id);
+    aNewCard->SetLocalId(id);
+
+    if (m_dbDirectory)
+      m_dbDirectory->GetUuid(id);
+    aNewCard->SetDirectoryId(id);
 
     mdb_err merror = m_mdbPabTable->AddRow(m_mdbEnv, cardRow);
     if (merror != NS_OK) return NS_ERROR_FAILURE;
 
   }
   else
     return rv;
 
@@ -1628,16 +1671,19 @@ NS_IMETHODIMP nsAddrDatabase::DeleteCard
   err = aCard->GetPropertyAsUint32(kRowIDProperty, &rowOid.mOid_Id);
   NS_ENSURE_SUCCESS(err, err);
 
   err = m_mdbStore->GetRow(m_mdbEnv, &rowOid, &pCardRow);
   NS_ENSURE_SUCCESS(err,err);
   if (!pCardRow)
     return NS_OK;
 
+  // Reset the directory id
+  aCard->SetDirectoryId(EmptyCString());
+
   // Add the deleted card to the deletedcards table
   nsCOMPtr <nsIMdbRow> cardRow;
   AddRowToDeletedCardsTable(aCard, getter_AddRefs(cardRow));
   err = DeleteRow(m_mdbPabTable, pCardRow);
 
   //delete the person card from all mailing list
   if (!bIsMailList)
     DeleteCardFromAllMailLists(rowOid.mOid_Id);
@@ -2902,16 +2948,24 @@ nsresult nsAddrDatabase::CreateCard(nsIM
     {
         nsCOMPtr<nsIAbCard> personCard;
       personCard = do_CreateInstance(NS_ABMDBCARD_CONTRACTID, &rv);
       NS_ENSURE_SUCCESS(rv,rv);
 
         InitCardFromRow(personCard, cardRow);
         personCard->SetPropertyAsUint32(kRowIDProperty, rowID);
 
+        nsCAutoString id;
+        id.AppendInt(rowID);
+        personCard->SetLocalId(id);
+
+        if (m_dbDirectory)
+         m_dbDirectory->GetUuid(id);
+        personCard->SetDirectoryId(id);
+
         NS_IF_ADDREF(*result = personCard);
     }
 
     return rv;
 }
 
 nsresult nsAddrDatabase::CreateABCard(nsIMdbRow* cardRow, mdb_id listRowID, nsIAbCard **result)
 {
@@ -2948,16 +3002,24 @@ nsresult nsAddrDatabase::CreateABListCar
 
         if (personCard)
         {
             GetListCardFromDB(personCard, listRow);
 
             personCard->SetPropertyAsUint32(kRowIDProperty, rowID);
             personCard->SetIsMailList(PR_TRUE);
             personCard->SetMailListURI(listURI);
+
+            nsCAutoString id;
+            id.AppendInt(rowID);
+            personCard->SetLocalId(id);
+
+            if (m_dbDirectory)
+             m_dbDirectory->GetUuid(id);
+            personCard->SetDirectoryId(id);
         }
 
         NS_IF_ADDREF(*result = personCard);
     }
     if (listURI)
         PR_smprintf_free(listURI);
 
     return rv;

new file mode 100644
--- /dev/null
+++ b/mailnews/addrbook/test/unit/test_uuid.js
@@ -0,0 +1,124 @@
+/* This file is testing that the UUID semantics of cards and directories match
+ * the guarantees of their documented requirements.
+ */
+
+var abMgr;
+/**
+ * Checks that the directory follows the contract for UUIDs.
+ *
+ * If the directory is modifiable, it will be modified, although the net effect
+ * will not change the state if the code works properly.
+ */
+function check_directory(directory) {
+  var prefId = directory.dirPrefId + '&' + directory.dirName;
+
+  var testModification = !directory.readOnly;
+  dump("Testing " + prefId);
+  if (testModification)
+    dump(" (with modifications)");
+  dump("...\n");
+
+  // Question 1: Is the UUID the preference ID?
+  do_check_eq(prefId, directory.uuid);
+  
+  // Now we need to run through the cards, checking that each card meets the
+  // requirements.
+  var seenIds = [], cards = [];
+  var enumerator = directory.childCards;
+  while (enumerator.hasMoreElements()) {
+    var card = enumerator.getNext().QueryInterface(Ci.nsIAbCard);
+    cards.push(card);
+
+    // Question 2.1: Is the directory ID correct?
+    do_check_eq(prefId, card.directoryId);
+
+    // Question 2.2: Is the local ID unique and valid?
+    do_check_neq(card.localId, "");
+    do_check_eq(seenIds.indexOf(card.localId), -1);
+    seenIds.push(card.localId);
+
+    // Question 2.3: Is the format equal to generateUUID?
+    do_check_eq(card.uuid, abMgr.generateUUID(prefId, card.localId));
+  }
+
+  // Question 3: Do cards returned via searches return UUIDs correctly?
+  var uri = directory.URI;
+  uri += "?(or(DisplayName,=,a)(DisplayName,!=,a))";
+  var search = abMgr.getDirectory(uri);
+  
+  enumerator = search.childCards;
+  while (enumerator.hasMoreElements()) {
+    var card = enumerator.getNext().QueryInterface(Ci.nsIAbCard);
+
+    // Question 3.1: Is the directory ID correct?
+    do_check_eq(prefId, card.directoryId);
+
+    // Question 3.2: Is the local ID valid?
+    do_check_neq(card.localId, "");
+
+    // Question 3.3: Is the format equal to generateUUID?
+    do_check_eq(card.uuid, abMgr.generateUUID(prefId, card.localId));
+  }
+
+  // The remaining tests deal with modification of address books.
+  if (!testModification)
+    return;
+  
+  // Question 4: Does adding a new card properly set the UUID?
+  var newCard = Cc["@mozilla.org/addressbook/cardproperty;1"]
+                  .createInstance(Ci.nsIAbCard);
+  newCard.displayName = "Test User";
+  newCard.primaryEmail = "user1@test.invalid";
+  newCard.firstName = "Test";
+  newCard.lastName = "User";
+
+  newCard = directory.addCard(newCard);
+  do_check_eq(newCard.directoryId, prefId);
+  do_check_neq(newCard.localId, "");
+  do_check_eq(seenIds.indexOf(newCard.localId), -1);
+
+  // Remove the new card to be stable!
+  var array = Cc["@mozilla.org/array;1"].createInstance(Ci.nsIMutableArray);
+  array.appendElement(newCard, false);
+  directory.deleteCards(array);
+
+  // We need to iterate over the array of cards to avoid any problems if someone
+  // makes the childCards enumerator reflect changes to directory...
+  for each (var card in cards) {
+    // Question 5.1: Does deleting a card properly set the uids?
+    var localId = card.localId;
+    array.clear();
+    array.appendElement(card, false);
+    directory.deleteCards(array);
+    do_check_eq(card.directoryId, "");
+    do_check_eq(card.localId, localId);
+
+    // Question 5.2: Does readding a card try to best-fit the uid?
+    card = directory.addCard(card);
+    do_check_eq(card.directoryId, prefId);
+    do_check_eq(card.localId, localId);
+  }
+}
+
+function run_test() {
+  // Preliminary: we need a directory for local tests
+  var testAB = do_get_file("data/cardForEmail.mab");
+
+  // Copy the file to the profile directory for a PAB
+  testAB.copyTo(gProfileDir, kPABData.fileName);
+
+  // Step 1: What is the ID of an empty card?
+  var newCard = Cc["@mozilla.org/addressbook/cardproperty;1"]
+                  .createInstance(Ci.nsIAbCard);
+  do_check_eq(newCard.uuid, "");
+  do_check_eq(newCard.directoryId, "");
+  do_check_eq(newCard.localId, "");
+
+  // Step 2: Check the directories
+  abMgr = Cc["@mozilla.org/abmanager;1"].getService(Ci.nsIAbManager);
+  var dirs = abMgr.directories;
+  while (dirs.hasMoreElements()) {
+    var directory = dirs.getNext().QueryInterface(Ci.nsIAbDirectory);
+    check_directory(directory);
+  }
+}