OK. If I got it right the app you're using is that provided by Google itself (that of the M icon over an envelope). If so, it is just a shortcut to the Gmail web interface. Try clicking the menu button and pick All mail. Most likely you'll find your deleted messages archived in this folder. Of course this depends on your current settings.