I ended up with "Implementation A" from my question. The amount of added time turned out to be trivial, owing chiefly to how fast Solr / Lucene is, I'm guessing.

This has proven to be quite sufficient under plenty of time serving production usage. And, in the event that it ever starts to be too slow, there are straight-forward caching options, to cache the result count for a given term : a majority of users' searches are for a fairly limited set of terms, and the result counts are stable for timeframes on the order of days or weeks.