This effecively means that Regex cannot be used to find a sequence of utf8-invalid bytes in a haystack of bytes.

That's incorrect. Here's a counter-example:

use regex::bytes::Regex;
fn main() {
 let haystack = b"foo bar\xFF baz";
 let re = Regex::new(r"(?-u)\xFF").unwrap();
 assert_eq!(re.find(haystack).map(|r| r.range()), Some(7..8));
}

Playground link.

I feel I am missing something big.

You might have missed this section in the docs: https://docs.rs/regex/latest/regex/bytes/index.html#syntax

The relevant sections there are:

The u flag can be disabled even when disabling it might cause the regex to match invalid UTF-8. When the u flag is disabled, the regex is said to be in "ASCII compatible" mode.

and

Hexadecimal notation can be used to specify arbitrary bytes instead of Unicode codepoints. For example, in ASCII compatible mode, \xFF matches the literal byte \xFF, while in Unicode mode, \xFF is the Unicode codepoint U+00FF that matches its UTF-8 encoding of \xC3\xBF. Similarly for octal notation when enabled.

While the pattern itself has to be valid UTF-8, you can match arbitrary byte sequences using hex escapes when Unicode mode is disabled.

But yeah this is a good question! This design was absolutely intentional and it is very much an important point that arbitrary bytes can be matched even though a regex pattern itself has to be valid UTF-8.

In theory, the implementation could be changed to support patterns that aren't valid UTF-8. Or even changed to parse straight from a &[u8]. But in practice this is usually not advantageous and it's better for comprehensibility reasons to just require that the pattern be valid UTF-8.