Para mover seus e-mails da pasta Lixeira para a Caixa de entrada ou qualquer outra pasta, use o botão Mover para :
Você pode selecionar todos os 100K e-mails na Lixeira selecionando todos os e-mails na primeira página e clicando no link Selecionar todas as mensagens xxx ... na parte inferior da página.
Esta imagem do Fórum de Ajuda do Gmail ilustra o que você precisa fazer: (clique na imagem para ampliá-la)