Did you upgrade the client lately, or is it the same client (6.0.3.8000) that he was using before when it worked?
Do the enterprise vault icons appear on the toolbar within Outlook?
Can you perfrom a search and open the items, or view them using archive explorer?