Below your undeleted messages should be two links, reading something like:

• And 970 more, 52 archived

Well, that's what mine looks like, anyway. ;-)

If you click on either link, you will be taken to one folder of your Message Inbox, either the default folder, or your archived messages.