This has happened over the past couple of months - I do a Reply and click on Delete so it'll Reply and Delete instead of going to Sent and it says = "The Message [blah blah blah] could not be moved to the mailbox "(bull)" - The destination mailbox does not exist" -- but there is a Trash mailbox so I know it exists. I just tried it again with a different message, same thing. However, if I select a message and hit Delete Selected it works.
This bug has been reported by others. No fix that I've seen. Happens intermittently to me, and I just ignore it. Only happens with delete upon send for me.