With Exchange 2003, it was easy. I could merely browse to https://servername/exchange/
[username]/[exchange folder name]/?cmd=Showdeleted
I'd love to be able to do the same in 2007, but I can't see how to do it.
Under Options-->Deleted Items I find only those items that were deleted from the Deleted Items folder.