But there are also higher complexity bounds on CFGs (since they include regular expressions, they certainly can't be lower).

In any case, I've never heard of someone using non-regular expression CFGs for lexing. Are there cases?

I mentioned Haskell above. It has nested block comments which should be balanced. Thus CFG.