Single multisite custom taxonomy creates multiple wp_term_taxonomy table entries

I've written a custom taxonomy for posts and pages on my WordPress Multisite installation as a short plugin. The code is as follows:

add_action('init', 'register_taxonomy_navigation_terms');

function register_taxonomy_navigation_terms()
  $labels = array(
    'name' => 'Navigation Terms',
	/* ... */
  $args = array(
    'labels' => $labels,
    'public' => true,
    'show_in_nav_menus' => true,
    'show_ui' => true,
    'show_tagcloud' => false,
    'show_admin_column' => false,
    'hierarchical' => false,
    'rewrite' => true,
    'query_var' => true,
    'capabilities' => array(
      'manage_terms' => 'navigation_terms_manage',
      'edit_terms' => 'navigation_terms_edit',
      'delete_terms' => 'navigation_terms_delete',
      'assign_terms' => 'navigation_terms_assign'
    register_taxonomy('navigation_terms', array('page', 'post') , $args);

The taxonomy is to be used for locating navigation pages across the entire network. I'm using Network_Query class from the Post Indexer plugin to do this.

I've noticed some strange things concerning this taxonomy.
First of all, I can activate and deactivate the plugin containing the taxonomy from network admin plugins panel, but I don't even see it from wither of site admin plugins panels.
Second issue is, at first the taxonomy had just one entry in wp_term_taxonomy table - now it has ~20 rows and that number is constantly growing.
Third and most important issue is that the query for pages and posts properly tagged with the taxonomy sometimes fails. It always works when querying for certain terms, and always fails when querying for certain others.
It seems that some of the terms are tagged using one of those "multiple taxonomies", and some are tagged using the others, but the query searches only for terms matching a certain term_taxonomy_id, and not all taxonomies by name, but that's only my hunch.

I also use User Tags for WordPress plugin ( to tag users with another taxonomy (representing positions they exercise in an NGO which I'm a member of) and there's the same error: the plugin containing the taxonomy is not visible on site plugins screen (even though I can access the plugin via a menu it adds to site dashboard), the taxonomy is duplicated multiple times in wp_term_taxonomy (6 times by now), and querying database for users based on user taxonomy (via $wpdb->get_results()) sometimes fails.

What's the real cause of this error and how to fix it?