Nodes stay "cached" in view after query should return false

I have a view that basically returns nodes tagged with whatever taxonomy term was given as an argument. The taxonomy term is not "multiple select" - only one choice allowed. If I change the taxonomy term of a node, it will be returned when the view is supplied the new taxonomy term as an argument (as expected) but also when the old taxonomy term is supplied.

I'm using views_embed_view to put the views into templates if that is relevant. However I tried the test on the view preview and the bug still exists there.

Not sure if this is a views or taxonomy issue.

Export of view

$view = new view;
$view->name = 'ordered_taxonomy_term';
$view->description = 'Ordered taxonomy term';
$view->tag = '';
$view->view_php = '';
$view->base_table = 'node';
$view->is_cacheable = '0';
$view->api_version = 2;
$view->disabled = FALSE; /* Edit this to true to make a default view disabled initially */
$handler = $view->new_display('default', 'Defaults', 'default');
$handler->override_option('fields', array(
  'title' => array(
    'id' => 'title',
    'table' => 'node',
    'field' => 'title',
    'label' => '',
    'relationship' => 'none',
    'link_to_node' => 1,
  ),
));
$handler->override_option('sorts', array(
  'field_importance_value' => array(
    'id' => 'field_importance_value',
    'table' => 'node_data_field_importance',
    'field' => 'field_importance_value',
    'order' => 'ASC',
    'relationship' => 'none',
  ),
  'created' => array(
    'id' => 'created',
    'table' => 'node',
    'field' => 'created',
    'order' => 'DESC',
    'granularity' => 'second',
    'relationship' => 'none',
  ),
));
$handler->override_option('arguments', array(
  'term_node_tid_depth' => array(
    'id' => 'term_node_tid_depth',
    'table' => 'node',
    'field' => 'term_node_tid_depth',
    'default_action' => 'not found',
    'style_plugin' => 'default_summary',
    'style_options' => array(
      'count' => TRUE,
      'override' => FALSE,
      'items_per_page' => 25,
    ),
    'wildcard' => 'all',
    'wildcard_substitution' => 'All',
    'title' => '%1',
    'default_argument_type' => 'fixed',
    'default_argument' => '',
    'validate_type' => 'none',
    'validate_fail' => 'not found',
    'depth' => '3',
    'break_phrase' => 0,
    'relationship' => 'none',
    'default_argument_user' => 0,
    'default_argument_fixed' => '',
    'default_argument_php' => '',
    'validate_argument_node_type' => array(
      'faq' => 0,
      'page' => 0,
      'photo_album' => 0,
      'story' => 0,
      'teaching_page' => 0,
      'term_summary' => 0,
      'testimony' => 0,
      'theme_sheet' => 0,
      'vocabulary_overview' => 0,
    ),
    'validate_argument_node_access' => 0,
    'validate_argument_nid_type' => 'nid',
    'validate_argument_vocabulary' => array(
      '4' => 0,
      '1' => 0,
      '3' => 0,
      '2' => 0,
    ),
    'validate_argument_type' => 'tid',
    'validate_argument_php' => '',
    'set_breadcrumb' => 0,
  ),
));
$handler->override_option('access', array(
  'type' => 'none',
  'role' => array(),
  'perm' => '',
));
$handler->override_option('items_per_page', 30);
$handler->override_option('row_plugin', 'node');
$handler->override_option('row_options', array(
  'teaser' => 1,
  'links' => 0,
));
$handler = $view->new_display('page', 'Page', 'page');
$handler->override_option('items_per_page', 30);
$handler->override_option('use_pager', '1');
$handler->override_option('path', 'ordered_term_view');
$handler->override_option('menu', array(
  'type' => 'none',
  'title' => '',
  'weight' => 0,
));
$handler->override_option('tab_options', array(
  'type' => 'none',
  'title' => '',
  'weight' => 0,
));
$handler = $view->new_display('block', 'Block', 'block');
$handler->override_option('items_per_page', 3);
$handler->override_option('style_plugin', 'list');
$handler->override_option('style_options', array(
  'type' => 'ul',
));
$handler->override_option('row_options', array(
  'inline' => array(),
  'separator' => '',
));

Live preview query

$view = new view;
$view->name = 'ordered_taxonomy_term';
$view->description = 'Ordered taxonomy term';
$view->tag = '';
$view->view_php = '';
$view->base_table = 'node';
$view->is_cacheable = '0';
$view->api_version = 2;
$view->disabled = FALSE; /* Edit this to true to make a default view disabled initially */
$handler = $view->new_display('default', 'Defaults', 'default');
$handler->override_option('fields', array(
  'title' => array(
    'id' => 'title',
    'table' => 'node',
    'field' => 'title',
    'label' => '',
    'relationship' => 'none',
    'link_to_node' => 1,
  ),
));
$handler->override_option('sorts', array(
  'field_importance_value' => array(
    'id' => 'field_importance_value',
    'table' => 'node_data_field_importance',
    'field' => 'field_importance_value',
    'order' => 'ASC',
    'relationship' => 'none',
  ),
  'created' => array(
    'id' => 'created',
    'table' => 'node',
    'field' => 'created',
    'order' => 'DESC',
    'granularity' => 'second',
    'relationship' => 'none',
  ),
));
$handler->override_option('arguments', array(
  'term_node_tid_depth' => array(
    'id' => 'term_node_tid_depth',
    'table' => 'node',
    'field' => 'term_node_tid_depth',
    'default_action' => 'not found',
    'style_plugin' => 'default_summary',
    'style_options' => array(
      'count' => TRUE,
      'override' => FALSE,
      'items_per_page' => 25,
    ),
    'wildcard' => 'all',
    'wildcard_substitution' => 'All',
    'title' => '%1',
    'default_argument_type' => 'fixed',
    'default_argument' => '',
    'validate_type' => 'none',
    'validate_fail' => 'not found',
    'depth' => '3',
    'break_phrase' => 0,
    'relationship' => 'none',
    'default_argument_user' => 0,
    'default_argument_fixed' => '',
    'default_argument_php' => '',
    'validate_argument_node_type' => array(
      'faq' => 0,
      'page' => 0,
      'photo_album' => 0,
      'story' => 0,
      'teaching_page' => 0,
      'term_summary' => 0,
      'testimony' => 0,
      'theme_sheet' => 0,
      'vocabulary_overview' => 0,
    ),
    'validate_argument_node_access' => 0,
    'validate_argument_nid_type' => 'nid',
    'validate_argument_vocabulary' => array(
      '4' => 0,
      '1' => 0,
      '3' => 0,
      '2' => 0,
    ),
    'validate_argument_type' => 'tid',
    'validate_argument_php' => '',
    'set_breadcrumb' => 0,
  ),
));
$handler->override_option('access', array(
  'type' => 'none',
  'role' => array(),
  'perm' => '',
));
$handler->override_option('items_per_page', 30);
$handler->override_option('row_plugin', 'node');
$handler->override_option('row_options', array(
  'teaser' => 1,
  'links' => 0,
));
$handler = $view->new_display('page', 'Page', 'page');
$handler->override_option('items_per_page', 30);
$handler->override_option('use_pager', '1');
$handler->override_option('path', 'ordered_term_view');
$handler->override_option('menu', array(
  'type' => 'none',
  'title' => '',
  'weight' => 0,
));
$handler->override_option('tab_options', array(
  'type' => 'none',
  'title' => '',
  'weight' => 0,
));
$handler = $view->new_display('block', 'Block', 'block');
$handler->override_option('items_per_page', 3);
$handler->override_option('style_plugin', 'list');
$handler->override_option('style_options', array(
  'type' => 'ul',
));
$handler->override_option('row_options', array(
  'inline' => array(),
  'separator' => '',
));