Systems and methods are disclosed herein that enable a client device to efficiently identify mailboxes containing objects of interest in a server-based message store. In some embodiments, a method of operation of a client device comprises sending a single request to a server for a list of mailboxes maintained by the server for a user that contain objects flagged with any of one or more flags specified in the single request. The method of operation of the client device further comprises, in response to the single request, receiving, from the server, the list of mailboxes maintained by the server for the user that contain objects flagged with any of the one or more flags specified in the single request. The method also comprises processing the list of mailboxes. In this manner, the client device is enabled to quickly and efficiently identify which mailboxes of the user contain objects of interest.