Lex was a dog. Flex, which as far as I know was a complete rewrite
that shared no code with lex, are not bad.

Yes, "it's true what they say about lex" was a common phrase.  (I think I first saw it in the pathalias paper.)

There was a Usenix presentation -- late 80's (Washington?) but I couldn't find it. -- by Vern Paxson about his rewrite called flex. I think he said that the main reason lex was slow was the clever folding it had to do of its internal tables to fit. Sadly Vern never got his paper in, but the presentation showed a group with three lines, one at the top being slow lex, the next two much lower on the Y axis being very close. He said the second line was flex. Someone said what about the third, fastest, line? His answer "that's cat"

Vern worked with Van on early network improvements (web-search the both of them for a fun time).

Flex first posted to Usenet in 1988, https://groups.google.com/g/comp.sources.unix/c/LZ_EHqd7XBg