That's where the in:anywhere search is your friend. It searches all mail.

What I mean is, the mandatory spam filter was so braindead it sent a reply to my own message to spam, which is itself absurd, but even moreso because the other party was also using Gmail