Using OR in WP_Query negates the “NOT EXISTS” compare

array(
  'relation' => 'OR',
  array(
    'key' => 'status',
    'value' => '', //<--- not required but necessary in this case
    'compare' => 'NOT EXISTS',
  ),
  array(
    'key' => 'status',
    'value' => 'new',
    'compare' => '=',
  ),
);

That should do it.