Blog Post
Priority Cleanup V2: Faster, Simpler Data Purging for Exchange Online
The requests to bring back Search-Mailbox speak to the need for speed when resolving something like a data spillage. Priority Cleanup is just too slow and ponderous in its current form - and I suspect that it will still be even with the enhancements being contemplated. One suggestion is have an initial "hide" pass where the search finds and hides mailbox items pending investigation. Removing items from user sight is a great start for many scenarios where Priority Cleanup might be used and it allows investigators and administrators the time to review items and decide on their final disposition without coming under pressure to resolve a problem.
Amen Tony. These requests always come with super high urgency as we race to remove the messages in a timely fashion. We had many pre-built search-mailbox queries that we could re-use (just changing the details) so could process these requests very quickly. Priority cleanup is just way to slow/bulky.