diff --git a/libempathy-gtk/empathy-images.h b/libempathy-gtk/empathy-images.h
index c714f04..06b1a01 100644
--- a/libempathy-gtk/empathy-images.h
+++ b/libempathy-gtk/empathy-images.h
@@ -30,7 +30,7 @@ G_BEGIN_DECLS
 #define EMPATHY_IMAGE_BUSY                "empathy-busy"
 #define EMPATHY_IMAGE_AWAY                "empathy-away"
 #define EMPATHY_IMAGE_EXT_AWAY            "empathy-extended-away"
-#define EMPATHY_IMAGE_UNKNOWN             "empathy-pending"
+#define EMPATHY_IMAGE_PENDING             "empathy-pending"
 
 #define EMPATHY_IMAGE_MESSAGE             "im-message"
 #define EMPATHY_IMAGE_NEW_MESSAGE         "im-message-new"
diff --git a/libempathy-gtk/empathy-ui-utils.c b/libempathy-gtk/empathy-ui-utils.c
index 2d8f409..1541ad9 100644
--- a/libempathy-gtk/empathy-ui-utils.c
+++ b/libempathy-gtk/empathy-ui-utils.c
@@ -209,8 +209,9 @@ empathy_icon_name_for_presence (TpConnectionPresenceType presence)
 		return EMPATHY_IMAGE_HIDDEN;
 	case TP_CONNECTION_PRESENCE_TYPE_OFFLINE:
 	case TP_CONNECTION_PRESENCE_TYPE_ERROR:
-	case TP_CONNECTION_PRESENCE_TYPE_UNKNOWN:
 		return EMPATHY_IMAGE_OFFLINE;
+	case TP_CONNECTION_PRESENCE_TYPE_UNKNOWN:
+		return EMPATHY_IMAGE_PENDING;
 	case TP_CONNECTION_PRESENCE_TYPE_UNSET:
 		return NULL;
 	}
diff --git a/libempathy/empathy-contact-manager.c b/libempathy/empathy-contact-manager.c
index ce77d27..f2bc219 100644
--- a/libempathy/empathy-contact-manager.c
+++ b/libempathy/empathy-contact-manager.c
@@ -36,6 +36,8 @@
 
 #define GET_PRIV(obj) EMPATHY_GET_PRIV (obj, EmpathyContactManager)
 typedef struct {
+	/* Owned (TpConnection *) => Owned (TpContactList *)
+	   The contact list associated with each connected connection */
 	GHashTable     *lists;
 	TpAccountManager *account_manager;
 	EmpathyContactMonitor *contact_monitor;
diff --git a/libempathy/empathy-tp-contact-list.c b/libempathy/empathy-tp-contact-list.c
index b936416..1c5122b 100644
--- a/libempathy/empathy-tp-contact-list.c
+++ b/libempathy/empathy-tp-contact-list.c
@@ -48,10 +48,27 @@ typedef struct {
 	TpChannel      *publish;
 	TpChannel      *subscribe;
 	TpChannel      *stored;
-	GHashTable     *members; /* handle -> EmpathyContact */
-	GHashTable     *pendings; /* handle -> EmpathyContact */
-	GHashTable     *groups; /* group name -> TpChannel */
-	GHashTable     *add_to_group; /* group name -> GArray of handles */
+	/* contact handle (TpHandle) => reffed (EmpathyContact *)
+	 *
+	 * Union of:
+	 *  - members of 'subscribe': we receive their presence
+	 *  - RP of 'subscribe': we asked to receive their presence
+	 *  - members of 'publish': we send them our presence
+	 *  - members of 'stored': they are in our roster
+	 */
+	GHashTable     *members;
+	/* contact handle (TpHandle) => reffed (EmpathyContact *)
+	 *
+	 * Contacts which are local-pending in the publish channel but are NOT in
+	 * the members hash table: they asked to receive our presence and we don't
+	 * receive theirs or asked to.
+	 * That's basically the contacts which asked to add us to their contact
+	 * list and we didn't answer it. */
+	GHashTable     *pendings;
+	/* group name: borrowed (const gchar *)  => reffed (TpChannel *) */
+	GHashTable     *groups;
+	/* group name: owned (gchar *) => owned GArray of TpHandle */
+	GHashTable     *add_to_group;
 
 	EmpathyContactListFlags flags;
 } EmpathyTpContactListPriv;
@@ -359,14 +376,14 @@ tp_contact_list_group_add (EmpathyTpContactList *list,
 }
 
 static void
-tp_contact_list_got_added_members_cb (EmpathyTpContactFactory *factory,
-				      guint                    n_contacts,
-				      EmpathyContact * const * contacts,
-				      guint                    n_failed,
-				      const TpHandle          *failed,
-				      const GError            *error,
-				      gpointer                 user_data,
-				      GObject                 *list)
+got_added_members_cb (EmpathyTpContactFactory *factory,
+		      guint                    n_contacts,
+		      EmpathyContact * const * contacts,
+		      guint                    n_failed,
+		      const TpHandle          *failed,
+		      const GError            *error,
+		      gpointer                 user_data,
+		      GObject                 *list)
 {
 	EmpathyTpContactListPriv *priv = GET_PRIV (list);
 	guint i;
@@ -378,9 +395,8 @@ tp_contact_list_got_added_members_cb (EmpathyTpContactFactory *factory,
 
 	for (i = 0; i < n_contacts; i++) {
 		EmpathyContact *contact = contacts[i];
-		TpHandle handle;
+		TpHandle handle = empathy_contact_get_handle (contact);
 
-		handle = empathy_contact_get_handle (contact);
 		if (g_hash_table_lookup (priv->members, GUINT_TO_POINTER (handle)))
 			continue;
 
@@ -389,15 +405,38 @@ tp_contact_list_got_added_members_cb (EmpathyTpContactFactory *factory,
 				     g_object_ref (contact));
 		g_signal_emit_by_name (list, "members-changed", contact,
 				       0, 0, NULL, TRUE);
+	}
+}
 
-		/* This contact is now member, implicitly accept pending. */
-		if (g_hash_table_lookup (priv->pendings, GUINT_TO_POINTER (handle))) {
-			GArray handles = {(gchar *) &handle, 1};
+static void
+add_to_members (EmpathyTpContactList *list,
+		GArray *handles)
+{
+	EmpathyTpContactListPriv *priv = GET_PRIV (list);
+	GArray *request;
+	guint i;
 
-			tp_cli_channel_interface_group_call_add_members (priv->publish,
-				-1, &handles, NULL, NULL, NULL, NULL, NULL);
-		}
+	if (handles->len == 0)
+		return;
+
+	request = g_array_new (FALSE, FALSE, sizeof (TpHandle));
+
+	for (i = 0; i < handles->len; i++) {
+		TpHandle handle = g_array_index (handles, TpHandle, i);
+
+		if (g_hash_table_lookup (priv->members, GUINT_TO_POINTER (handle)))
+			continue;
+
+		g_array_append_val (request, handle);
+	}
+
+	if (request->len > 0) {
+			empathy_tp_contact_factory_get_from_handles (priv->factory,
+				request->len, (TpHandle *) request->data,
+				got_added_members_cb, NULL, NULL, G_OBJECT (list));
 	}
+
+	g_array_free (request, TRUE);
 }
 
 static void
@@ -473,6 +512,29 @@ tp_contact_list_remove_handle (EmpathyTpContactList *list,
 }
 
 static void
+remove_from_member_if_needed (EmpathyTpContactList *list,
+			      TpHandle handle)
+{
+	/* remove contact from members if it's not in publish and subscribe */
+	EmpathyTpContactListPriv *priv = GET_PRIV (list);
+	const TpIntSet *members;
+
+	members = tp_channel_group_get_members (priv->subscribe);
+	if (tp_intset_is_member (members, handle))
+		return;
+
+	members = tp_channel_group_get_remote_pending (priv->subscribe);
+	if (tp_intset_is_member (members, handle))
+		return;
+
+	members = tp_channel_group_get_members (priv->publish);
+	if (tp_intset_is_member (members, handle))
+		return;
+
+	tp_contact_list_remove_handle (list, priv->members, handle);
+}
+
+static void
 tp_contact_list_publish_group_members_changed_cb (TpChannel     *channel,
 						  gchar         *message,
 						  GArray        *added,
@@ -487,6 +549,7 @@ tp_contact_list_publish_group_members_changed_cb (TpChannel     *channel,
 	guint i;
 
 	/* We now send our presence to those contacts, remove them from pendings */
+	add_to_members (list, added);
 	for (i = 0; i < added->len; i++) {
 		tp_contact_list_remove_handle (list, priv->pendings,
 			g_array_index (added, TpHandle, i));
@@ -494,8 +557,10 @@ tp_contact_list_publish_group_members_changed_cb (TpChannel     *channel,
 
 	/* We refuse to send our presence to those contacts, remove from pendings */
 	for (i = 0; i < removed->len; i++) {
-		tp_contact_list_remove_handle (list, priv->pendings,
-			g_array_index (removed, TpHandle, i));
+		TpHandle handle = g_array_index (removed, TpHandle, i);
+
+		tp_contact_list_remove_handle (list, priv->pendings, handle);
+		remove_from_member_if_needed (list, handle);
 	}
 
 	/* Those contacts want our presence, auto accept those that are already
@@ -579,28 +644,59 @@ tp_contact_list_subscribe_group_members_changed_cb (TpChannel     *channel,
 {
 	EmpathyTpContactListPriv *priv = GET_PRIV (list);
 	guint i;
+	GArray *accept;
 
 	/* We now get the presence of those contacts, add them to members */
-	if (added->len > 0) {
-		empathy_tp_contact_factory_get_from_handles (priv->factory,
-			added->len, (TpHandle *) added->data,
-			tp_contact_list_got_added_members_cb, NULL, NULL,
-			G_OBJECT (list));
-	}
+	add_to_members (list, added);
 
 	/* Those contacts refuse to send us their presence, remove from members. */
 	for (i = 0; i < removed->len; i++) {
-		tp_contact_list_remove_handle (list, priv->members,
-			g_array_index (removed, TpHandle, i));
+		remove_from_member_if_needed (list, g_array_index (removed, TpHandle, i));
 	}
 
 	/* We want those contacts in our contact list but we don't get their
 	 * presence yet. Add to members anyway. */
-	if (remote_pending->len > 0) {
-		empathy_tp_contact_factory_get_from_handles (priv->factory,
-			remote_pending->len, (TpHandle *) remote_pending->data,
-			tp_contact_list_got_added_members_cb, NULL, NULL,
-			G_OBJECT (list));
+	add_to_members (list, remote_pending);
+
+	/* Implicitly accept pending request of contacts which are now members. */
+	accept = g_array_new (FALSE, FALSE, sizeof (TpHandle));
+	for (i = 0; i < added->len; i++) {
+		TpHandle handle = g_array_index (added, TpHandle, i);
+
+		if (g_hash_table_lookup (priv->pendings, GUINT_TO_POINTER (handle)) != NULL)
+			g_array_append_val (accept, handle);
+	}
+
+	for (i = 0; i < remote_pending->len; i++) {
+		TpHandle handle = g_array_index (added, TpHandle, i);
+
+		if (g_hash_table_lookup (priv->pendings, GUINT_TO_POINTER (handle)) != NULL)
+			g_array_append_val (accept, handle);
+	}
+
+	tp_cli_channel_interface_group_call_add_members (priv->publish,
+		-1, accept, NULL, NULL, NULL, NULL, NULL);
+
+	g_array_free (accept, TRUE);
+}
+
+static void
+tp_contact_list_store_group_members_changed_cb (TpChannel     *channel,
+						gchar         *message,
+						GArray        *added,
+						GArray        *removed,
+						GArray        *local_pending,
+						GArray        *remote_pending,
+						guint          actor,
+						guint          reason,
+						EmpathyTpContactList *list)
+{
+	guint i;
+
+	add_to_members (list, added);
+
+	for (i = 0; i < removed->len; i++) {
+		remove_from_member_if_needed (list, g_array_index (removed, TpHandle, i));
 	}
 }
 
@@ -724,6 +820,9 @@ list_ensure_channel_cb (TpConnection *conn,
 	/* TpChannel emits initial set of members just before being ready */
 	if (!tp_strdiff (id, "stored")) {
 		priv->stored = channel;
+		g_signal_connect (priv->stored, "group-members-changed",
+				  G_CALLBACK (tp_contact_list_store_group_members_changed_cb),
+				  list);
 	} else if (!tp_strdiff (id, "publish")) {
 		priv->publish = channel;
 		g_signal_connect (priv->publish, "group-members-changed",
diff --git a/libempathy/empathy-utils.c b/libempathy/empathy-utils.c
index 3acd470..ebbcf05 100644
--- a/libempathy/empathy-utils.c
+++ b/libempathy/empathy-utils.c
@@ -245,8 +245,9 @@ empathy_presence_get_default_message (TpConnectionPresenceType presence)
 		return _("Hidden");
 	case TP_CONNECTION_PRESENCE_TYPE_OFFLINE:
 		return _("Offline");
-	case TP_CONNECTION_PRESENCE_TYPE_UNSET:
 	case TP_CONNECTION_PRESENCE_TYPE_UNKNOWN:
+		return _("Unknown");
+	case TP_CONNECTION_PRESENCE_TYPE_UNSET:
 	case TP_CONNECTION_PRESENCE_TYPE_ERROR:
 		return NULL;
 	}
