You can search specific labels by using "label:" or for mails in trash with "in:trash". Actually, "is:", "in:" and "label:" all mean the same thing so "is:spam" "in:spam" and "label:spam" will return identical results. They work for labeled email, email statuses (read, starred) and for spam and trash. To search every single email use "in:anywhere". By default Gmail won't search deleted emails and emails marked spam.