Well, notmuch doesn't delete messages itself by design. But you can delete messages by other means, using tags to designate the messages you want deleted. This really doesn't seem to be a big hurdle.

"cannot have copies in multiple folders ... no notion of folders"

I hear people talking about notmuch and folders a lot, and I can understand why if they're still using other clients to access their mail -- clients that can't deal with mail using just tags. But if you've moved completely to using notmuch, then using tags only and forgetting about folders seems like the way to go.

"cannot apply a tag to an individual message without passing by the threaded view first"

If you have the message open, you should be able to apply a tag to it using (notmuch-show-add-tag).

That said, I have my own gripes with notmuch:

Notmuch doesn't have scoring, it doesn't have BBDB integration, it has no way to get arbitrary message headers from elisp, it only indexes a handful of headers, it can't do regex searches of everything.