When messages are deleted they are put in the Deleted Items folder. You should look in here for deleted messages. If you open the folder you may find it still in there and you can Recover it.
When they are deleted from this folder they are then stored on the Exchange server for an extra 7 days (this is not used as part of your quota - size).
Also if they are not in there, highlight the deleted items and go to Tools>Recover Deleted Items – it is possible you maybe able to retrieve your deleted item from here. Highlight the relevant item and press restore – this will restore your deleted item back to where it came from.