I tried this on a few accounts in TB 60.3.1, and each time Edit/Undo (Ctrl+Z) restored the deleted message. It's either instant or takes a few seconds, depending on the service (all tests done with IMAP accounts with IMAP Trash or Deleted).

Is this happening with a Gmail account? Gmail has some quirks as far as deleting, marking as deleted, etc.

Does the same thing happen in safe mode? Hold Shift when you launch TB.

Thank you, sfhowes!

This is POP mail from my own server. No remote folders involved.

I hadn't tried safe mode. Yes, that fixes it. But a bunch of buttons are missing across the top - Reply, Delete, etc.

Maybe I added them as customizations a decade ago or something.

If it works properly in safe mode, you probably have either an incompatible add-on or the layout was broken (other possibilities revealed by safe mode are less likely). If you find it's not an add-on, you can fix the layout by launching in safe mode, checking 'Reset toolbars and controls', and clicking 'Make changes and restart'. That will restore a 'default' layout in normal mode which you can modify as below.

Select View/Toolbars/Customize and drag buttons to and from the Mail Toolbar and drag and drop them in the desired position.

Got it! Thank you so much, sfhowes!

That really was annoying...

I'm not sure what fixed it. I think (90% sure) it was the very first trip through safe mode that unglued the bug.

But I also removed some incompatible add-ons I'd forgotten about years ago. And after the first Safe mode visit, the button mismatch seemed to go away between normal and safe.

Anyway - fixed! :) Thank you!