Do new routes require a static first portion? Using mymodule.routing.yml, I can successfully create a custom route at /foo/{bar}/{baz}, but I cannot use /{bar}/{baz} or /{bar}/foo/{baz} as path for a route; they just return a 404 error.

Why? Is there any way to create a route for /{bar}/{baz} (with strict requirements for bar)?

I've read the entirety of the routing API and I can't seem to find any answers.
In the routing system you can't do this. What you can do is path aliasing.

Inbound: /{bar}/foo/{baz} -> /foo/{bar}/{baz}

Outbound: /foo/{bar}/{baz} -> /{bar}/foo/{baz}

You need a pattern to apply a regular expression on the path inbound, so /{bar}/{baz} is only possible if the parameters themselves have a distinctive pattern.

I didn't find a tutorial how to build a path processor, but you can use the 
PathProcessorFront class as example. 

Register both as tagged service in the .services.yml file for the module.

services:
  path_processor_front:
    class: Drupal\Core\PathProcessor\PathProcessorFront
    tags:
      - { name: path_processor_inbound, priority: 200 }
      - { name: path_processor_outbound, priority: 200 }
    arguments: ['@config.factory']