objects.delete doesn't remove completely
Selecting the objects and letting bpy.ops.object.delete() remove them may not be a good idea, not least due to the performance of the bpy.ops calls. Maybe you can get the list of the selected objects using bpy.context.selected_objects. Then iterate over the objects and call:

for obj in bpy.context.selected_objects:
    if(obj.type == 'MESH'): #Maybe this is superfluous in this case
        bpy.context.scene.objects.unlink(obj)
        #material.users count is not reduced yet, even if object is gone from the scene
        bpy.data.meshes.remove(obj.data)
        #now material.users count is reduced by one
        #(Just be careful with the above call, since multiple objects can share the same data)
        bpy.data.objects.remove(obj)