Is there a way that a user can Search in All Documents and then see which folder a message resides?
Subject: Not by default
There is no default functionality to show what folder a message resides in after a search from All Docs. You could make a view for this, though.
Subject: try the Discover Folders feature
Click on the Folder action and then select “Discover Folders”. A dialog box will appear showing you a list of the folder(s) a message is in.
In 8.5, we added a “Folder” column to the All Documents view, which shows this information by default.