So are all the old email addresses and new email addresses still in active directory for that user? If so we should be able to show you all the mail.
I am guessing you just created a new email policy for all your users to create the new email address. If so then you need to call support to see why you are not seeing all the mail probably.
Sorry for the misunderstanding.Go to the full post