We'd probably do it via altering the actionlog hooks to be able to reverse from human-friendly labels, to codenames, and then inject them as alternates in the search query. That would mean altering all the hooks, and any new hooks doing that too.
Alternatively, we could do an in-memory search - essentially return everything from the DB, and see what labels evaluate against our search term.
Alternatively, we could cache the labels in the table - but this would waste space, and assume one particular language.

Personally I don't think it's worth it, given the complexities there and given that the user can still find what they need by just searching particular types without parameters and scanning over, or by seeing the human-friendly labels on the Admin Zone home page and then clicking on the date there.