I have contacts with either two email addresses or they get a new email address. I list and save both email addresses but history does not show for both.
Does this situation happen in Outlook client? If so, to rule out Outlook client problem, I recommend you go to Outlook Web App to check if the contact in OCM shows the same.
Meanwhile, to help us understand your symptom more clearly, may I bother you to share a screenshot of the history page here so we can perform test at my side?