I was envisioning that the maybe-returning version would be a separate method, equivalent to the current two-return-value variant, which of course already has that overhead.

Having the default return a 'maybe' would be a possibility; I'm pretty sure the practical performance difference would be completely negligible, given all the other stuff a map lookup has to do, but it might have worse ergonomics. In that case you'd probably want a builtin optional-unwrapping operator like some languages have, so it's not too verbose if you expect the element to be there.

> Is there any language where a map/set access returns an optional/maybe?

Swift is one. It has ! as an unwrap operator, along with other syntax sugar for optionals, so it's not verbose:

      5> let q = ["a": "b"]
    [snip]
      6> q["a"]
    $R2: String? = "b"
      7> q["x"]
    $R3: String? = nil
      8> q["a"]!
    $R4: String = "b"
      9> q["x"]!
    fatal error: unexpectedly found nil while unwrapping an Optional value