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.