we've got a recent problem users are reporting that Outlook 2012 SP1 is forgetting their recently used email addresses. In previous versions these were saved in the nk2 file but I think thats changed with 2010. The setting to keep them rememebered is enabled and indeed it has been working since we upgraded to 2010 back in 2009 or whenever.
Its only just recently started. Ive not released any updates for these machines this year so can rule that out.