John,
I think you are going to have to create a support case with symantec for this issue.
Just so you know, when you open up Archive Explorer, the left hand pane which is the folders is driven from the database, and when you click one of those folders, the items generated in the right hand pane are driven from the index.
So rebuilding the index would not generate a missing folder list.
this also means that an item in Archive Explorer will show the original locaiton it was archived, and not where the shortcuts may reside.
So for instance if you archived \Inbox\mySubFolder, but then created \inbox\ArchivedItems\ and moved all your shortcuts there, Archive Explorer would still show \mySubFolder
If you right click the Folder List , you should have a Refresh button, you may luck out and it just be caching old information, or if you are using Offline Vault it may not be an up to date view of Archive Explorer
What i would do is first confirm through Browser Search and using Full Details on the search results to find the item, and in the details of the results you should see the location , for instance \inbox\mySubFolder
This technote may point you in the right direction, but would sooner recommend creating a case with symantec
cheers