Did you know you can actually relink an existing history to a different contact? (Doing this will "move" the History to the new contact)
1. Find the History item you wish to re-link (everything excepting e-mails is allowed).
2. Right click on the History Item and select Properties.
3. Click on the little black arrow button to the right of the Contact Name, near the top of the History dialog window.
4. The Search Center will now prompt you to search for the appropriate Contact, do so normally, then double-click on it.
The History is now linked to the Contact you just searched for, and this change should be reflected in the associated History tab.