Filter out posts before display category count

As pointed out by @Jagst3r15, you’re going to have to loop through each category’s posts no matter what to filter out those posts that hold your meta key.

For a high-level answer: I’d suggest looking at the INNER JOIN logic that happens in _pad_term_counts() for an example of how to bring in the posts table. Then filter on the get_terms hook to loop through those results and exclude what you don’t need.

It’s a good question with a not-very-simple answer, unfortunately.