
At this point, I would humbly expect to get a Delete Forever button, instead of the Delete one. After all, the button was there right before I made the search. Oh well, I'll just click Delete.

A ha, that was a waste of time, just like I imagined - the action Delete applied on a conversation that's already in the Trash, will unnecessarily move it to the Trash.
I could select the needed messages, go and click on Trash again, and forever delete them from there, but that's a little counter-intuitive.
I just added my suggestion regarding this issue, at the Gmail: Help Center. I don't feel like searching the Gmail dedicated Google Group(s) for this one, sorry.