I use smart mailboxes on my Mac. I also extensively use mail filters to sort my mail into numerous folders locally on my Mac. So most of my mail doesn’t remain for long in iCloud. I generally don’t delete mail from smart mailboxes, but when I do they get moved into my local Trash folder and no longer appear in the smart mailbox, which doesn’t include the Trash folder. So the kind of situation you are complaining about works as expected for me. Perhaps, though, that is because I’m dealing almost exclusively with mail stored locally on my Mac.
There could be something related to the email provider. I was recently helping my father manage his overflowing Yahoo inbox using Apple Mail. I had searched on a newsletter email address as the sender, and tried to delete the 100’s of messages that matched, but they would pop back up. Watching the Activity window, it appeared that the “Moving messages to trash” action wouldn’t complete.
I think some of the messages ended up deleted (i.e., I may have noticed that the 100’s were slowly diminishing) from each pass. I ultimately selected a page’s worth of messages at a time for deletion, and that seemed to work.
Is it possible that Yahoo doesn’t allow mass deletes like that through IMAP?
As a workaround, in case you haven’t already thought of it, instead of deleting the messages directly from the Smart Mailbox, you might try first moving them via a keyboard shortcut to an On My Mac folder you create for that purpose (I call mine Pre-Trash), then deleting them from there.
EDIT: “an On My Mac mailbox” (not folder)