I fixed my problem by creating new collections (which obviously don't contain the deleted object), selecting an empty which shall receive the new collection as the instancing property and using a simple script
for obj in bpy.context.selected_objects:
obj.instance_collection = bpy.data.collections["newCollection"]
Afterward I found out I could have done the same via
Select Linked (Shift+L) \
Instanced Collection and editing the property while holding
Alt (to apply it to all selected objects).
I still have the now unused collections in the blend-file and can't seem to get rid of them plus I was searching for a way to edit the original collections so I see this as a workaround and leave the question open for additional answers.