How to run code when object is removed from world?

The answer should straight-up be: Just use the AncestryChanged event. While this works if the new Parent is another object, it does not get triggered when Part is removed from world (when own or ancestor's Parent is set to nil).

I would expect AncestryChanged to be triggered if Parent (or any ancestor's Parent) is set to any new value, no matter if the new value is nil or anything else.

To verify the fact that AncestryChanged does not get triggered when setting to nil, put this script in your workspace and Run:

local part = Instance.new('Part')
part.Parent = workspace

wait(1)

local changed = false
part.AncestryChanged:Connect(function(obj, parent)
	changed = false
end)

part.Parent = nil

print('Removed part. AncestryChanged triggered: ', changed)

I am now using workspace.DescendantRemoving with a bunch of ifs, but this is not as elegant, and what's worse is that it also gets triggered when just changing Parent's, which is not what I want at all.

You could use a .Changed event on the object and see if the property that was changed was the Parent property...

local object = workspace.Object

object.Changed:Connect(function(property)
	if property == "Parent" then
		if object.Parent == nil then
			...
		end
	end
end)