Fastest way of counting posts of a custom post type in a specific taxonomy term?

Terms generally should have a count parameter that you can use. I’m not sure if this is accurate across multiple post types though.

This may not be the fastest solution but one option could be the additional parameters for WP_Query to both reduce the number of queries and the returned values. 10up has a good article on this in regards to WP_Query Performance. An example query could look like this:

$the_query = new WP_Query( array(
    'post_type'     => 'post',
    'no_found_rows' => true,
    'tax_query'     => array( array(
       'taxonomy'   => $taxonomy,
       'field'      => 'term_id',
       'terms'      => $term->term_id
    ) ),
    'no_found_rows' => true,    // Don't calculate pagination
    'fields'        => 'ids',
) );

You could cache the results until the next time terms are added too using the added_term_relationship hook which you could take advantage of to speed up future requests.