When you delete a message in an IMAP account, it is merely marked for deletion, which only happens when you expunge folder (via Actions | Expunge from the menu, for example). Until then, Evolution simply hides messages marked for deletion so they don't obstruct your view.
As long as deleted messages are not expunged yet, they can be undeleted. But to undelete them, you first have to see them.
Undelete Messages in an IMAP Account in Evolution
So, to undelete messages in an IMAP account in Evolution:
- Select View | Hide Deleted Messages from the menu to make sure it is not checked.
- Emails marked for deletion should now appear in your folder, stricken out.
- Highlight the messages you want to undelete.
- Click on the selection with the right mouse button.
- Select Undelete from the menu.