Sorry to say, but from what you described, you've deleted that message.
If it is "delete now", the message is actually deleted right at that moment, not moved to [Deleted].
You have three options for "delete":
1. Delete now
2. Move to [Deleted]
3. Hide on the phone, keep on the server.
While you can do either of them through the 3-dot menu, in the settings, you configure one of them to be the default, i.e the one that is assigned to the Delete icon (and you can also assign one to one of the swiping options).