Deleting an object part of a collection does not remove it from the collection
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

import bpy

bpy.ops.object.select_linked(type='DUPGROUP')
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.