All mail in Gmail is in the All Mail label, unless the message is deleted. Even Inbox is just a label. When you add or remove a label, the email is still in All Mail, it just also shows up in the other label if it's labeled.
Note: even All Mail is a label, it just is the only one that can't be removed (except by deleting the message).
I had a similar question to this so I ran a test. I put both incoming and outgoing emails into a label called test and then deleted the label. The sent email was still in the sent label and the other that should have reverted to the inbox was not there. I was able to search it and find it but could not find the label. I noticed it had an arrow symbol pointing to the right so I looked down in the list of labels and notice one called "important" with a similar arrow. I believe the arrow I saw meant the message was forwarded but it still led me to the important label because the symbol is similar. I went into this label and there was the email I was looking for.
Now trying to find a way to make these revert back to the inbox.