HELP! Our scrum team is losing credibility

What timeframe are stakeholders looking for if it isn't a Sprint, and how are each of your 4 Product Owners managing those expectations?

I don't think it's safe to say that you "work according to the Scrum framework":

• You have 4 "Product Owners". In Scrum, the "Product Owner is one person, not a committee". There are many cases where a single person cannot manage a product on their own due to the combination of the broad set of required skills or the amount of work involved. However, there should be one single Product Owner.
• "Within a Scrum Team, there are no sub-teams or hierarchies." It appears that you have at least two sub-teams - developers and testers.
• Sprints should not be planned ahead. You should have a long-term Product Goal and a Product Backlog, but Sprints should be planned one Sprint at a time and feedback received at the Sprint Review or from people using past released Increments should be incorporated into the Product Backlog. The most valuable work should be the most well-refined and ready for a Sprint.

However, I'm not sure that these are at the heart of the problem you're facing.

What strikes me as confusing is that you say that you have 4-week Sprints, you release every 4 weeks, but your stakeholders are giving feedback that you're not delivering the Increments on time.

Is the underlying problem that 4 weeks is too slow? If so, then invest in trying to have shorter Sprints and releasing more frequently. Although you claim that work won't fit into a Sprint if it's shorter than 4 weeks, I find that very difficult (but not impossible) to believe. However, there may be some prerequisite work needed to enable the team to slice work into smaller increments and deliver more quickly.

Is the underlying problem that the work delivered in 4 weeks isn't of sufficient value (e.g., the team costs more to fund for a 4-week Sprint than the value of the work delivered)? Perhaps delivering every 4 weeks is sufficient, but the value delivered needs to be increased. There are several options, from a mismatch between the Product Goal and the Sprint Goal, a poorly ordered Product Backlog, mismatches between stakeholder expectations and the Sprint Goal, or impediments that cause the team to put forth a large amount of effort for a small amount of value.

I'd start with a stronger definition of the problem. Who is the feedback coming from and what would they like to see?

Echoing @Thomas' sentiment, I have a few questions.

1. Who cares if a story can't be done in less time than 4 weeks? Why can't you provide some usable, value of the whole need in 2 weeks in order to get feedback?
2. Why do you need 4 POs? Is the team really working on 4 different products?
3. Does your team work in the model of developers do their work and then hand it off to testers to run a large set of regression tests? Have you considered any alternate methods of doing the testing?
4. Does your "quite accurate" 3 month roadmap actually reflect the wants and needs of the stakeholders? Could that be why they are complaining that you are not delivering on time?

We're looking into ideas to change our narative with stakeholders. What would you reccomend?

I'd recommend abandoning any narrative and start having ongoing conversations. Include the stakeholders as an extension of the team. Use them to validate that the work being done by the team is what they need. Give them incremental valuable, usable deliveries as fast as you can so that they can give you feedback you use to adapt that "quite accurate" 3 month roadmap. The Scrum Guide states that multiple increments can be created during a single Sprint.  Deliver increments as they are ready instead of waiting for the end to do so.

When I mention incremental I mean this. Don't try to give them a feature that will allow them to manage their inventory, run 14 different reports, trigger 9 different alert emails, and order them a lunch from different locations each day all at once.  Find out what is most important for them from that list. Work on that and only that.  Such as provide the interface for viewing the inventory.  See if it provides the information they want in a way that they like.  Then introduce the ability to update the information. Next is two of the reports that they need most. Follow that with the ability to trigger alert emails based upon the information in those two reports.  Etc, etc, etc...

In your original post, you only mentioned the stakeholders at the end when you said you wanted to "change our narrative".  Maybe it would be better to change your relationship with them. 

To respond to your questions: 

@Ian Mitchell: 
Q: "What timeframe are stakeholders looking for if it isn't a Sprint, and how are each of your 4 Product Owners managing those expectations?"

A: Our product is too big to be managed by one person. Wether you call them 'product owner' or a different job title. We do however share one development team. 

@Daniel Wilhite

1. Q: "Who cares if a story can't be done in less time than 4 weeks? Why can't you provide some usable, value of the whole need in 2 weeks in order to get feedback?"
   A: Probably a couple of reasons: 
   - our developers give the feedback they are not able to work efficiëntly in code nearby of each other. Meaning sprints for a new module could look like this: Sprint 1: API endpoint, Sprint 2: blank new front-end page, Sprint 3: Fill of front-end etc.
   - Our sprints are not 100% focussed on our big projects. There's always Tech Dept and smaller stories directly from our customer
    
2. Q: "Why do you need 4 POs? Is the team really working on 4 different products?"
   A: See answer to Ian Mitchell above
    
3. Q: "Does your team work in the model of developers do their work and then hand it off to testers to run a large set of regression tests? Have you considered any alternate methods of doing the testing?"
   A: Our developers do their work, a second developer reviews, then a their tester tests and does a regressiontest before a release
    
4. Q: "Does your "quite accurate" 3 month roadmap actually reflect the wants and needs of the stakeholders? Could that be why they are complaining that you are not delivering on time?"
   
   A: The new modules that we are delivering are being sold, and used well. So that would indicate that at least what we are delivering meets their needs. But I can only say this for the bigger modules we're developing, not the smaller increments we are able to easiliy fit into one sprint. 
   
   Here's an example timeline of a recently released module: 
   - Q1-Q2 2023 there where multiple co-creation sesions with clients. 
   - Q1 2024 ~10 of those participants signed a 'special interest group' contract, meaning they commit to purchasing the subscription in advance and provide feedback so the product matches their needs. In return they receive a discount for a period of that contract. 
   - Q2 2024 to Q3 2024: First deliverable was developed & tested on a demo page by the special interest group. 
   - Q1 2025: second deliverable, incl improvements from feedback first deliverable. Customers tested again
   - End Q1: Third and final deliverable, incl improvements from feedback
   
   What happens each sprint next to delivering a bigger increment (such as a module): 
   - Each sprint there's room for tech dept (10%)
   - Each sprint we give our cusomer support team 10% to pick up smaller bugs and increments
   - Each sprint we improve the accesability of our platform (legal requirement) 10%
   - There's the dependency of front-end and back-end developers in our team
   - THere's the inefficiëncy when our developers have to work in the same code (which I think they find frustrating so steer clear of that too) 
   
   What happens at forecast meetings with our management & with clients: 
   - Promises are made on developing a module to specific clients
   - There's no clarity on what we're going to do, wich could give our client the feeling their feedback dissapears into an "black box"
    

Our product is too big to be managed by one person. Wether you call them 'product owner' or a different job title. We do however share one development team. 

Product Ownership is about accountability, regardless of whoever has the responsibility for managing a product. That accountability is not a committee and cannot be subdivided.

From what you describe, no one person is accountable for ensuring that stakeholders receive the timely delivery of value each Sprint, and that may be part of the problem.

Based on some of this, I see several problems that, if addressed, could help with the situation:

• You absolutely need one single Product Owner for the product. Product management, regardless of the complexity of the product, is often too expansive for one person to have the knowledge and the skills to perform. A complex product only adds to the complexity. However, there is immense value in having a single accountable person as the Product Owner who has the final decision making authority when it comes to evaluating all of the possibilities, ordering the Product Backlog, and justifying the ordering. The well-ordered Product Backlog should give transparency into the next things being worked on by the team. The use of flow metrics can be helpful in forecasting when work in the Product Backlog would likely be delivered.
• Make sure that your Product Owner is ordering the Product Backlog appropriately. Although setting aside percentages of time for tech debt and bugs may look good on paper, it's usually insufficient. Work gets muddied, especially if the Sprint Goal becomes at risk. Look at why you're injecting tech debt and defects and how to prevent that, but also consider setting aside more time to pay down these problems before building new features and functionality on top of low-quality work.
• If you're relying on manual regression testing, stop. Invest in test automation. You'll be able to run your testing much earlier in the cycle, which will allow you to identify potential issues (with the tests or with the product - any failing test would need to be evaluated). Developers should be cross-trained in test automation and helping to backfill existing test cases and creating at least some test cases in parallel with new development to cover key flows.
• The Developers need to develop the skills and the environment needed to have thin vertical (end-to-end) slices of work that can be delivered quickly. It's not clear to me if the problems are more in how the work is being decomposed and designed or past technical decisions, making it difficult to vertically slice the work, but the Developers should be in a position to figure that out and come up with a plan.

Thanks for the additional information.  I usually try to avoid this but I'm going to be one of those people this time.

Your organization doesn't want the benefits of using the Scrum framework.  They don't want to change to make it work.  Instead they want to command-control the process. The organization does not want to look deep into their behavior and identify ways to improve cooperation and reaction. Your developers do not want to work as a team. They want to be individual heroes that own specific parts of the code. Each one wants to write code that others have to use instead of a team of people that write code together. 

Everything that @Ian, @Thomas, and I have said above comes from experience with the Scrum framework and introducing it into organizations. We have seen the success and failure. Honestly, if I worked at your company in your position, I'd probably just abandon the Scrum framework entirely and focus on creating some home-grown processes/methods that would allow the company to move forward.  Focus on flow metrics like @Thomas suggested.  Read the books from Daniel S. Vacanti (https://actionableagile.com/books/). See if there is anything in those books that can help you evaluate your current situation in a way that can help lead to change. Read up on Kanban and eXtreme Programming searching for techniques and practices that could be useful for your organization. You may even look into hiring an external consultant that can come in, observe, and help your organization improve. Make sure that you are not the only individual that is doing all of this research.  Have the Developers participate since they are the ones that do the most intensive part of the work. 

I am not sure what industry your products are targeted towards.  But I have worked on products for stock trading, insurance, IT Help Desks, social forums, massively multiplayer online games, publishing, medical office management, manufacturing/distribution, real estate, database administration, network administration, and others.  I have only experienced one that could not break their product offerings down into small enough units that a single person could be responsible for the unit's future direction, a single team of 4-8 developers could be responsible for all changes made (including testing), and delivery of updates could be made continuously (sometimes multiple updates per day). It takes work and the willingness to change the organization in order to get to those abilities. 

What happened to the one that couldn't do it?  They went bankrupt because all of their competitors were able to deliver more aggressively. The product that it had was widely used, many organizations paid for it. There were over 6 million active users on a daily basis.  But the competitors were able to provide new functionality and better experience on a much faster cadence at a price that was equal or sometimes less. 

It may be that your organization is not as I see it.  If that is true I hope they are able to make the changes you need.  The suggestions above this post are good ones that I hope are valuable to you.  And I expect that others may provide suggestions after this post.  Take them all into consideration and work with your own organization to change as it can. Good luck and let us know how things turn out. That is how we all learn.  Do something, inspect the outcomes, adapt as necessary.  Empiricism in action.