Why can’t I do a Deep Traversal (subfolder) Search on the MAPI Public Folder Tree?

Your other choices include archiving the public folder stores into a nearline system that includes a decent index / FTI. Try KVS as a good starting point - I work there and would say that, but you'll find that KVS are Microsoft's key GTM partner around archiving for FY05.(http://directory.partners.extranet.microsoft.com/SolutionPage.aspx?i=41&cat=0&SolutionID=2364&pid=5&vid=0)