That is why it has to be synchronized as I mentioned in the first post, in which process these records would be rearranged as required by the business rules. This could be as easy as those that come first to the online db, keep the position and the new ones are moved, or even by sorting this by created date etc.
In the end, if we were to create a char/varchar key for all tables, we would run into exactly the same issue. There is cases where a relationships would have no natural key, in these cases you are stuck with GUID (horrible btree performance) or a homegrown algorithm for making it (could be everything from collision issues to btree issues), in this case you resort to a surrogate key anyway just making it a varchar/char instead of int.
No matter how we look at this, a sync and journal system has to be created. This system has to follow the business rules, and handle all the odd cases that could happen like the ones we have discussed. Which type is used (surrogate/natural) does not really matter, both has their pros and cons which has to be handled and addressed.