Bedrock will not re-create records that had been previously deleted in a given system.
The reason we do not do this is to protect users from having records added back into their systems where they had been deleted. While there can certainly be scenarios where you delete and then want to re-add these contacts back, since our platform has to go with the scenario that is more likely to accommodate all of our customers, we opted to avoid re-creating deleted contacts.
So what do I need to do in order to let these contacts sync again over to the system where I had deleted them?
You will need to perform a Reset of your sync. This will clear out the history of the deleted records in your Bedrock integration.