Embodiments are directed to determining in an email data store which of a plurality of email mailboxes is searchable, to searching multiple mailboxes in an email data store and to preserving data items that are placed on hold. In an embodiment, a web service receives a request to determine which among many different email mailboxes is available for searching. The web service allows multiple different programs to search the email data store. The web service sends a query to the email data store to determine which email mailboxes are available for searching. The web service also returns a list of those email mailboxes which are searchable in the data store. The searchable mailboxes have an appropriate, specified version and permissions indicating that the mailbox is searchable.