What seems important and relevant here is that you want your record to be the MASTER RECORD and your ID to External ID used by the orgs you'll be sending records to. Email addresses by their very nature are automatically external Ids for Contacts, so no sweat doing an upsert for Contacts regardless of whether dupes already exist in two or more orgs that have same Contact saved with different Ids and an "indexer generated external Id". You can always use the email address as the external Id in those situations.
But what do you do about the accounts they're associated with? I'm going to assume they're associated with business accounts as you didn't say if this is B2B or B2C. If B2B, the Account may or may not have the same unique email associated with the Account you can use as an external Id. The indexer generated Id in each org will be unique. That means you'll have more than one indexer generated Id you'll need to keep track of in YOUR database. Further, your record ID isn't being directly kept as the Master Record ID (indirectly, yes, but not directly).
Trying to update or resolve these external Ids if you try to merge them could be a real hassle for you and your end users/customers. As a customer, I wouldn't particularly want to deal with that hassle unless you had a way to automate it for me.
Perhaps there's a 3rd way that you've not considered which is to import their database into yours, assign a Master Record Id to it and do the same as you import data from other customers. If it exists, you merge it with existing records and push those updates using the existing Master Record Id.
For each new customer, you'll initially have the set-up hassle of bringing in their database with their Salesforce recordIds, finding matches in your database and where they exist, adding your existing Ids as the external Id. Where they don't, you create a new record and assign an external Id to it. That same database then gets exported to and imported into the your user's database which in the meantime has had the external Id field added to it. In that way, ever org gets the same external Id which corresponds to your Master Record Id. After the import is done, you can dump the temporary database of their original records as you'll have integrated it into your master database.
Is that more work for you? Yes, it would seem to me that it would be. Does it maintain a cleaner database for all? I would think it does.
From a Salesforce database standpoint, upserts are slower and create a higher load on the system than doing a push of new records for insert. That's something which is well documented. Just don't ask me to provide you with a link to it right now as I can't remember off-hand where that documentation can be found. I only know that I've seen it numerous times. I think it's in some of the dataloader related materials.
I hope this analysis is helpful to you in coming up with a solution that meets your and your customer's needs. As with most things, I don't believe there's always one "best practice" solution, instead only methods that either don't work well at all or are insecure vs methods that are of increasingly efficiency; the latter of course only applies when security is maintained. Sometimes the "ideal" simply isn't practical or affordable for most organizations, making it an unrealistic expectation or standard to hold an organization to.