You have an X/Y problem. You have a client that can't or won't expend the time, effort, or cost needed to define the work, but wants a fixed price. You're trying to solve for "how can we provide a fixed price for fixed requirements within an agile framework," but your real problem is that you have too many unknown unknowns to do this. Either address that head-on, or you and the client must both accept the risk that the project is likely to fail.
Analysis and Recommendations
[E]ither an estimate has been performed and failed to capture all of the required features, or the estimating process has been deemed too expensive to do thoroughly...[so the project] has fixed requirements[.]
To paraphrase, you have a legacy system. No one has a full set of specifications, understands the whole system, or is able to maintain it. They want a work-alike, but can't or won't define what that actually means.
This isn't really a "rebuild." It is essentially a feature-by-feature port to a new system, which may include new technologies, languages, hardware, infrastructure, and any number of other things. Even if you had a complete list of specifications for the functional and non-functional aspects of the legacy system (which you don't) you would be hard-pressed to estimate this fundamentally new work on anything other than a time-and-materials basis.
Agile frameworks like Scrum are based on incremental and iterative development leading to emergent design and/or implementation. So, there's no reason you can't use an agile approach, but you and the client must both accept a priori that you are building a new system to implement poorly defined business rules that support existing processes rather than simply swapping out black box components.
Let's set aside whether or not the existing rules and processes should change as part of this effort. If I were in charge, that's where I would start, rather than simply trying to re-implement a legacy system. That's me, though; if the customer is not open to doing things better then you have to address the fact that this amounts to building a new work-alike rather than a "rebuild" or a "re-implementation."
First, have this conversation with your leadership, and let them have it with the client. The pros and cons of any approach and a clear definition of success are must-haves before you fully engage, and the only way to get there is through communication.
Secondly, push for a multi-phase engagement where the first part is a deep-dive assessment. This is likely to involve:
- Interviewing users to find out what the system does for them and how they use it.
- Putting the existing system under test in some way, even if it's just high-level behavioral tests with Cucumber or the like.
- Clearly define the contractual presumption that without some form of system testing to define a Definition of Done or "seams" in the system (Working Effectively with Legacy Code. Feathers, Michael. Pearson, 2004.) you cannot guarantee a specific or successful result.
- Design a first phase of the project where the deliverable is simply a scope and specification document. It doesn't matter if this is a set of specification documents or an agile Product Backlog; the point is you need inputs that will feed work breakdowns and project planning for follow-on phases either way.
- Define the second phase as planning for the third phase. You may or may not be able to roll that into the first or third phase, depending on whether you're doing waterfall or agile, but "planning the plan" in some degree is needed either way.
In the third phase, you either have a complete set of specifications and OKRs to work from, or you build the system using just-in-time planning and just-enough architecture and engineering processes to build the system in small-but-measurable increments that you can inspect and adapt collaboratively with the client.
Pros and Cons
If you take the agile approach, the client gets frequent chances to inspect the work in progress and fine-tune the requirements, implementation details, and the Definition of Done. This doesn't guarantee them a successful project, but it allows them to avoid cost overruns, sunk costs, and deliverables that are not fit for purpose by terminating the project early (thereby saving money) if it isn't going to succeed or is already sufficient even if not necessarily 100% complete.
Because agile projects are based on what is essentially a fixed periodic run-rate of unknown total length, they can also choose to extend the project if they like the results, but it's taking longer than expected. That's the whole point of Sprints, Planning Increments, or whatever your framework uses: it's an inspect-and-adapt opportunity to determine the net present value of the expended costs, and to estimate (not guarantee) the remaining costs to get to "satisfactory" or "good enough" rather than 100% complete.
On the other hand, all-or-nothing approaches can be viable, but lead to someone eating the costs if the project is bases on faulty assumptions, invalid estimates, or anything unexpected and not part of the original plan. This leads to change orders, cost overruns, or deliverables that aren't fit for purpose. It also leads to contractual arguments, which are rarely constructive and largely the domain of the legal departments, and if you get there then the project is pretty much a failure whether you ultimately deliver the thing or not.
The Manifesto for Agile Software Development explicitly values:
Customer collaboration over contract negotiation[.]
for precisely this reason. A hands-off customer that can't or won't collaborate with you to define the work upfront or throughout the course of development is essentially asking you to either accept all the risk, or is forcing you to present a contract with so many explicit assumptions, stipulations, and strategic exit clauses that no one will be happy. It's essentially a document that expects failure, and in this case the likelihood of failure is much greater than the industry average of 68%.
If they aren't going to be collaborative, and both the legacy system and new system are both poorly defined, then both parties are essentially buying a pig in a poke. This is more than just a bad idea. It's pretty much a planned failure where everyone involved can expect failure after sunk costs, unpaid work, death marches, and unmet expectations. And then the legal fun begins!
The Iron Triangle or Quadrangle
The theorem stipulates that you can't fix all aspects of a project at the same time. Anytime you tweak an aspect such as:
you impact the others. At least one of these elements must always be flexible. Most agile frameworks prioritize adjustable scope, but other frameworks make different trade-offs.
If you offer a fixed-price, fixed-scope, fixed-schedule contract, then quality and fitness for purpose is the element most likely to suffer. And of course, if you haven't stipulated the trade-offs, you're back to contractual and legal wrangling.
No one wants to have these conversations, but not having them is worse. Part of running any successful project requires making the process as transparent as possible, which means that someone has to be courageous enough to initiate honest conversations about what's required for the project to be successful, not just for one party or the other to buy a pig in a poke.
Changing Your Process Improves the Chances of Success
Think of this as a teachable moment for both your company and the client. By changing the way your company approaches projects like these, regardless of the project management framework used, you can better serve your clients and allow them to make better business decisions as well.
The framework doesn't matter. It's the effectiveness of communications, transparency, and setting of expectations that will set the tone for the project. Those three things are also what make the project more or less likely to succeed.