Don't know if this works in your case, but could you define a custom property to a mail item when you start tracking it. Then define a unique track id, for example new guid, to the property. Later on you could find the location of the mail item using this custom property as long as you know the track id you gave it. Whenever you find the message in a new location, record the new path somewhere (of course the initial path must be saved when you give the track id)
More info:
http://msdn.microsoft.com/en-us/library/bb147619(v=office.12).aspx[
^]