Yes, this will indeed be a problem. I think that generally having globally unique ids is better, especially if you want auditing, but if you can't have that, then I guess you'll have somehow to "archive" the old entries.
One possibility is of course to simply remove the history. You can issue a bulk sql operation: delete from MyEntity_AUD e where e.originalId.id = :newId. But then there's a problem of also deleting all the related entities etc.