What are some of the methods to clean that up?
Inbox rule to delete the messages. Sounds like an OK thing to do. Took 4 hours for the rule to run. Yeah that is helpful.
Use the Compliance Center of Office 365 ? That is closer, but through the management console you can find the messages but putting a legal hold is not quite what I had in mind.
It turns out that you can use the Search-Mailbox powershell command with a -DeleteContent to remove the email from the users mailbox. You will need some of the Compliance Center permissions for the cmdlet to show up for you.
Using remote powershell connected to your Office 365 Tenant you can run the following command:
get-mailbox <users mailbox> | Search-mailbox -SearchQuery 'Subject:"Insert Subject Line"' -DeleteContent
The SearchQuery has a few options to use to search the mail, subject, to, from, and attachments.
Hey that is a little easier, since you don't have to open the users mailbox to place a rule inside it.
There is a limit to the number of items in the search query, it is limited to 10,000. So if you have more matches you will need to run multiple times. This still takes time to run. I have found it does run faster off-peak hours. (Unscientific)