Views Taxonomy Term argument to represent "no term"
Just in case anyone else stumbles upon this answer, we solved this problem with the following approach:

function MODULENAME_views_query_alter(&amp;$view, &amp;$query) {

  if($view-&gt;name == 'your_view_name')){

    //Flip the term table join to a LEFT join
    $view-&gt;query-&gt;table_queue['term_node_value_0']['join']-&gt;type = 'LEFT';

    //CLear the extra condition (removes a where clause on the join limiting only matching term ids)
    $view-&gt;query-&gt;table_queue['term_node_value_0']['join']-&gt;extra = null;

    //Look through the where clauses and add a null condition clause
    if($index = array_search('term_node_value_0.tid = %d', $query-&gt;where[0]['clauses'])){
      $query-&gt;where[0]['clauses'][$index] .= ' OR term_node_value_0.tid IS NULL';
    }
  }
}


It changes the JOIN type to a LEFT join, removes the limiting clause from that join and adds a condition to match against null values.  It's obvious limitation is that it should be using aliases instead of hard coding the field name.

The function should go in your modules views.inc file where Views expects to find this hook.