The order of the events if pretty clear (ItemAdding – ItemAdded – ItemUpdating – ItemUpdated, and others e.g. when you delete, emailReceived, WorkflowStarted, etc.), but how many there are triggered could differ depending on the application (e.g. WebUI, Word document Save as, and more important - custom implementations!).
E.g. while working on properties screen (after Upload) - there is a ItemUpdating going on, pressing Cancel at that screen causes this event NOT to occur.
In your case, of course ItemUpdated would be the best, but you need to make sure you block Event Firing while you do your operation (because ItemDeleting/-ed and ItemUpdating/-ed would trigger in loop) and also make sure you check for Content Approval being enabled and/or Versioning, as you need to CheckOut the actual file before manipulating it.
You could do an actual COPY of the document at the destination and run a DELETE on the Source (what about metadata - r u sure you get same properties on the destination?). If you plan to use it across SITES, do not use SPFile.MoveTo() as to my knowledge it only works on current subsite.
Have you considered also relying on Content Organizer to do it for you automatically and only set appropiate Metadata in your Handler?