I selected an email in the Spam folder and clicked 'Not Spam'. I expected it to go into the Inbox. But I cannot find it anywhere, even when I use Search. So, where do 'Not Spam' emails go?
Every time I have clicked "Not Spam" the spam label has been removed and the inbox label has been added. Any other labels that have been attached by filters will stay with the message.
In other email services I have seen spam with strange dates so it could be on a different page of your inbox.
If you are using the Gmail Categories feature it could be in any of the 5 Tabs.
Some other places to look:
Is it possible that the system attached it to an existing conversation. I have not seen this happen, but it is possible.
Have you looked in "All mail"? This catch-all label has everything except spam.