... if they were to apply the new TKU and rescan, new objects would be created in Discovery and CMDB, and old ones MarkAsDeleted in CMDB. This is as designed, and expected. However, the problem comes when they have Change, Problem and other records attached to the old (to-be-deleted) CIs. This info will be lost.
That should only happen in the BMC.ADDM dataset. When the standard OOtB ADDM ReconciliationJob runs, it should identify correctly the CIs already present in BMC.ASSET, match the ReconciliationIdentity and merge (update) the CIs, so the AM/IM/CM relationships should not be lost.
I strongly suggest testing this in a Test Environment with a small subset if they have concerns about the procedure.