--- a/src/core/xmpp.py	Fri Apr 24 14:54:24 2015 +0200
+++ b/src/core/xmpp.py	Fri Apr 24 14:57:09 2015 +0200
@@ -181,6 +181,7 @@
 
     def rosterCb(self, roster):
         assert roster is not None # FIXME: must be managed with roster versioning
+        self._groups.clear()
         self._jids = roster
         for item in roster.itervalues():
             if not item.subscriptionTo and not item.subscriptionFrom and not item.ask:
@@ -239,6 +240,15 @@
     def setReceived(self, request):
         #TODO: implement roster versioning (cf RFC 6121 §2.6)
         item = request.item
+        try:  # update the cache for the groups the contact has been removed from
+            left_groups = set(self._jids[item.entity].groups).difference(item.groups)
+            for group in left_groups:
+                jids_set = self._groups[group]
+                jids_set.remove(item.entity)
+                if not jids_set:
+                    del self._groups[group]
+        except KeyError:
+            pass  # no previous item registration (or it's been cleared)
         self._jids[item.entity] = item
         self._registerItem(item)
         self.host.bridge.newContact(item.entity.full(), self.getAttributes(item), item.groups, self.parent.profile)