Removing “trashed” posts from post count in custom taxonomy terms?

This is a known, reported WordPress bug.

There are some workarounds, such as this one:

add_action( 'edited_term_taxonomy','wpse26548_edited_term_taxonomy', 10, 2 );
function wpse26548_edited_term_taxonomy($term,$taxonomy) {
  global $wpdb,$post;
  //in quick edit mode, $post is an array()
  //in full edit mode $post is an object
  if ( is_array( $post ))
    $posttype=$post['post_type'];
  else
    $posttype=$post->post_type;
  if ($posttype) {
    $DB_prefix=$wpdb->get_blog_prefix(BLOG_ID_CURRENT_SITE);
    $sql = "UPDATE ".$DB_prefix."term_taxonomy tt
          SET count =
          (SELECT count(p.ID) FROM  ".$DB_prefix."term_relationships tr
          LEFT JOIN ".$DB_prefix."posts p
          ON (p.ID = tr.object_id AND p.post_type="".$posttype."" AND p.post_status="publish")
          WHERE tr.term_taxonomy_id = tt.term_taxonomy_id)
          WHERE tt.taxonomy = '".$taxonomy->name."'
      ";
    $wpdb->query($sql);
  }
}

You may also need to add the following to your register_taxonomy() arguments array:

'update_count_callback' => '_update_post_term_count'

Note that these are completely untested.

(See also: this related WPSE question)