Deleting with NOT EXISTS vs NOT IN gives different results
Your address_id columns contain nulls, and thus you got caught by the three-valued logic of SQL.

https://www.postgresql.org/docs/current/static/functions-subquery.html#functions-subquery-in describes the behaviour of IN:


  Note that if the left-hand expression yields null, or if there are no equal right-hand values and at least one right-hand row yields null, the result of the IN construct will be null, not false. This is in accordance with SQL's normal rules for Boolean combinations of null values.


And of course NOT applied to null is null, not true, see https://www.postgresql.org/docs/current/static/functions-logical.html