If this is a GMail account, you will find the message in the All Mail folder.
No it is not a gmail account, what about other accounts?
Not sure Colin. I thought that GMail was the only one that used categories for mimicking folders. Maybe check with your email provider.