I've created a handy utility that drives the Data Loader to export all custom object data in an org including relationships as proper references to the corresponding external IDs, then it can import that data into a fresh org in correct dependency order.  This works great for all of our custom objects because they all have external ID fields.  However, one of our objects has a lookup relationship with the standard User object, and I'm not sure what to do about that.  I know that I could add a custom field to User and mark it as the external ID, but we're an ISV delivering a managed package, so I'd strongly prefer to avoid anything that requires custom fields on standard objects unless they're driven by explicit business requirements and not a technical workaround.

Obviously one issue here is that user IDs are tied to specific orgs, so externalizing org-specific information into something that is otherwise completely portable across orgs is probably a bad idea.  Maybe that alone is a reason for a separate external ID field on User that correlates a user in one org with the same user in another org.

Has anyone dealt with this specific issue before?  Any thoughts on the best way to address it?

Thanks!