If a linked record is deleted from one database, it will not be added back the next time Synchronization runs.  The record in the other database will remain intact and Synchronization will remove the Integration ID from the record the next time it is run, which indicates the remaining record is an unlinked record.