Discoverability is a red herring
I disagree with the notion that rotating examples can "work against discoverability". I agree that examples can help inform new users of functionality and thus increase discoverability. However, if examples are rotating, discoverability isn't reduced. A new user will still be exposed to some functionality they may not be aware of, so, the degree of discoverability remains constant. Furthermore, rotating examples can increase discoverability for regular users because different examples will reveal new functionality.
One legitimate issue with the rotating example is that it may be a needlessly indirect method of revealing functionality. But, an example feature is one of many ways of revealing new functionality to the user. So, this is only a challenge to discoverability if it's the only approach in use.
Nonetheless, an approach I've seen that benefits discoverability is used by OneLook dictionary. OneLook's homepage displays a list of example searches beneath the search box on the home page. This means that anytime I show up to search I know what all my options are without having to seek them out.
OneLook could have revealed these different search types using rotating examples but it would then take the user more than a dozen visits to the home page to be exposed to all of them.
Objectively speaking, a rotating example shouldn't be any more confusing than a similarly designed static example. Both example types can be potentially confusing or have a number of other usability issues if poorly designed. The OESI approach given by the OP has usability issues due to the example search being provided as a placeholder.
Sometimes placeholders do not disappear when users move their input focus into the field. If the placeholder remains in the field as editable text, users are forced to manually select and delete it. This creates an unnecessary burden on users and increases the interaction cost of filling in the form.
Compare this to the official page for the Ruby programming language which implements rotating code examples. The display box shown below gives a random code example when the page is loaded.
I know this isn't a search example, but imagine if it were, would it be any less confusing if the example stayed the same?
Discoverability, confusion and other usability issues are irrelevant when considering the suitability of rotating examples over static ones. These issues will only matter when we take your design into consideration.