What is the correct way to set cache contexts on custom blocks?
In most cases, you just set the cache context directly on the render array you return in your build() method.

I have finally found what my issue was, with the help of @Berdir and @4k4.  If you are using a custom template, such as block--myblock.html.twig and you output the variables individually, such as {{ content.foo }} instead of all at the same time like {{ content }}, it ignores your cache contexts passed directly into your block build array, when logged out.  See What is the correct way to set cache contexts on custom blocks?

So, to answer the original question:

1) Cache contexts passed directly into a custom block plugin are sometimes ignored.  You can test this by altering the SyndicateBlock, and then creating a custom template in your theme block--syndicate.html.php in which you output the variables individually like this:

{% block content %}
  {{ content.foo }}
{% endblock %}


As you change the url arguments, you'll see the block doesn't respect the cache context.

Now if you change it output all the content as a piece, it works:

{% block content %}
  {{ content }}
{% endblock %}


Now, it respects the cache context, and the block is unique per page.

2)  For now, to work around this, you can just output what's in your block in it's own template.

 public function build() {

    $search_form = \Drupal::formBuilder()-&gt;getForm('Drupal\mymodule\Form\SearchForm');
    return [
      '#theme' =&gt; 'mycustomtemplate',
      '#search_form' =&gt; $search_form,
      '#cache' =&gt; ['contexts' =&gt; ['url.path', 'url.query_args']]
    ];

  }


This circumvents the block module's esoteric caching exceptions and your form is now unique per page when logged out.

3) Should you create your own theme template to fix this, or just add a method for getCacheContexts() in your custom Block plugin?  It's better to create a new theme template, rather than add a getCacheContexts() method that overrides the natural order of bubbling up of cache contexts, and may break metadata deeper in your build array.