Regarding your experiences:
Every company wants to innovate, even those companies who start businesses in heavily-diluted market sectors and flat-out copy the business models of other well-established companies. They are gambling on their ability to innovate by being able to do the same work better, faster, or cheaper than their competition.
The definition of "innovate" is simply "to make changes [or] do something in a new way". That's it. It doesn't necessarily mean being on the bleeding edge. It doesn't necessarily mean introducing a new product. It can be as mundane as changing the text of a button (which in some circumstances can double or triple conversions), tweaking the pricing/terms of an existing product, or marketing to a different niche.
These are all what I would call examples of business innovation; they're not really technical or design innovation. A lot of people didn't think there was anything particularly innovative about Twitter at first, until the network effect took hold and people could effectively create their own customized real-time newsreels.
My point is that you're using the term "innovation" to refer to something else. It's not entirely clear from your question what that something is... but you need to figure it out, and soon, because, as the famous quotation goes, what we've got here is failure to communicate.
What do you want?
You are presenting some vision to prospective employers/clients, they are hiring you based on that impression, and you are later finding out that it was a poor match. Clearly you didn't ask the right questions if you were surprised, and perhaps the answers you gave them were vague or misleading as well, if they were surprised.
What is your vision? What do you consider innovation? Figure out how to express that in the least subjective terms possible, and you will have a much clearer and less negative explanation of what went wrong.
For example, my twin career goals have always been to establish myself as a technical leader and to work on a product (or products) that will improve the quality of life for a lot of people. I've moved around a bit, but always with that clear goal. When I left my first job after nearly 10 years, it was because the company had not expressed any plans to expand the technology team - scratch goal #1 - and considered itself a service- rather than product-oriented organization, with the product only existing to support the service - scratch goal #2.
At no point did it ever feel awkward or negative discussing these points in an interview, because (a) these are not negative traits in every company, and (b) I only bothered speaking to employers who were actually expanding their teams and actively developing at least one semi-useful (IMO) product.
I am sure that my goals are not everyone's goals; you need to decide on what your goals are, and then it will be clear to you why your previous employers weren't a match and why a future, prospective employer might be. Then it's an easy conversation because you just have to tell the truth, you don't need to hold back or come up with euphemisms.
Asking the right questions:
First of all, your cover letter (do people still even use those?) should never elaborate on why you left or are considering leaving your current position. Because, frankly, the recruiter or hiring manager doesn't give a damn. They care why you're interested in their position; if you can't express that without referring back to your previous position, then you're an immediate no-hire.
But let's assume you move onto some interviews. Don't ask dumb questions like "are you willing to innovate?" because, as I said in the first paragraph, every company is. It's like asking "do you want to make money?" Of course they do, but you didn't specify how much or how often, and even then they might not be very good at it or even understand what's required.
In fact, hiring managers are probably already asking you the exact same questions you need to be asking them if you want to understand how they really work. For example:
- What's the long-term vision for this company?
- What do you imagine the role of [insert department name here] being in 5 years?
- Why are you looking for a [insert job title here]? Is this a replacement or a new role?
- What do you think makes [company name] better or more successful than its competitors?
- Is there anything that [company name] is aiming to get better at?
- If I were employed in this role and wanted to introduce a new [tool/product/process], who would I have to convince and what would it take to convince them?
- It's 2 weeks before the deadline and all 10 people on the team insist that it will be impossible to finish on time. What do you do?
- Pretend that I just came up with an idea which, if successful, could make you millions of dollars every year. But it would take 2 months to implement and cost $250k, and would only have a 10% chance of succeeding. Would you do it? Why or why not?
Recognize any of these? You should, they're mostly the exact same questions that almost every hiring manager asks you, just flipped around. Believe me, executives spend a lot of time thinking about this stuff, and most reasonably-competent hiring managers should either already know the answer to many (not necessarily all) of them or offer to get back to you on it. The interview isn't just for them to see if you're qualified, it's also for you to see if it's the sort of place you'd want to work.
These seem like really obvious questions, but I know that most candidates don't ask them, because interviewers always seem to be surprised when I do. It's amazing how much you can glean about a company's overall attitude just from asking a handful of totally generic questions. None of these are offensive or inherently negative questions, and collectively they will tell you a lot more about a company's definition of "innovation" than asking them that question directly.
If that's still not enough info, then go back to your goals, and think about more hypothetical questions that you could ask in order to find out if you see eye-to-eye with their corporate leadership.
P.S. I know some people will say that the HR person who interviews you is just going to say "I don't know" to a lot of these questions, and if you're interviewing for a very junior position then you probably either shouldn't ask them or suck it up if you get a non-answer back. But if they're recruiting for a senior position - presumably the kind of position where you could make a real difference - then it's not uncommon to get a short interview with someone from senior management, and not unreasonable to request one if you don't. They are, after all, the people who will largely dictate your career growth potential.