A simple workaround would be to temporarily move all of your deleted messages to a new folder ("Zombies") and search within that. Then, when you're done with whatever you're moving about, just delete the folder, which will (once again) delete all of the messages within it.
You can (directly within the email interface), add a new contact if the contact is the sender of the email (the "From" field). However, the contacts in the cc and bcc cannot be directly added to your contacts.
The quickest way of doing this individually for those 30 contacts you have would be to use the desktop version of Outlook (tested with Outlook 2013). Within here, you can hover on each persons email to add them to your contacts and then add them to the group.
Best Answer
The command you're looking for is actually in the message menu next to the "Reply" button.
Click the down arrow to open the menu.
Choose "View message source"
That'll give you the raw email message, including all the headers.