Ideally (not that this would ever happen) the third party service (e.g. App.net) would be able to query Twitter as to the veracity of each user's archive (verify an md5 hash or whatever kids use these days) then allow the tweets to be backdated into their system.

I imagine that dealing with the t.co URLs, and mentions by/conversations with Twitter users who aren't on App.net, or use a different name, would be a problem too.