If you use the global search: in the search results tab click on "Show results as list" in the upper right corner. This will display the search results as list in a new tab. Add the "Location" column in the list headers so can identify the "missing" folder, then R-click on the message > Open > Open message in containing folder. This way you'll see where the missing folders is located.