Pull out common removal code, and detect does-not-exist correctly