It seems like Agile would have been a great fit. Too many requirements, no real information - it's exactly the situation where throwing out prototypes and getting feedback can lead to a solution.
Here is where the outsourcing happening in this story comes back to bite, though. It's basically impossible to write a good contract for an Agile development process. (The only time I've seen it at all is in gov't work, where cost-plus is the default way to pay, and it doesn't often produce good software.)
If I'm the customer, why would I accept anything less than X for the amount of money I'm paying, and if I'm the developer, then Y is a perfectly good MVP, and since X >> Y, who determines when you are finished?
Contracts for non-Agile processes are pretty worthless too if the project happens like this. If I understand correctly, the client ended up swallowing the cost for being intentionally lied to.
In an Agile process, the client would be much more closely involved with the development, attend sprint reviews, ask questions, and be available for questions about whether to drop features or extend the deadline. The client can make an informed decision and sound the alarm when too much time is spent on things they don't need.
It can work, and it has to, because the vast majority of companies in the world simply cannot write their own software. The problem is big software companies that mostly exist to leech of those other companies' lack of understanding of software. Basically every company that outsources software still needs to have at least one person who understands software development and project management sufficiently to keep an eye on the development process and check that they're not being scammed.
I don't think hiring some certified Agile gurus and reshuffling all the teams in the middle of the project would have improved the chances of delivery.
It depends if you do certified Agile™ or apply some core agile principles. Getting something that works ASAP and then iterate is a huge win whenever possible. Losing steam on a project that hasn't met any useful milestone yet must be one of the main sources of waste in our industry. Granted, 15 months in might make it tough to correct course towards a shippable milestone. Definitely worth the exercise tough.
Agile is great for running execution teams and gives you real-time feedback on progress, but if you have a contract with fixed scope and timeline, you're just boxed in. Agile requires flexibility on time and/or scope and it's not amenable to a services contract unless you have a very trusting customer.
It's not clear how long the project lasted but it was at least 3.5 years. So the time-line couldn't have been that rigid; yes there was a Gantt chart but those are like horoscopes. And since the requirements kept coming in there was no fixed scope.
As far as the customer goes you can say something like "we'd like to deliver a prototype early" and then it sounds like you're exceeding the contract. You just have to get them to prioritize features while avoiding discussing the fact that it's impossible to deliver all the features they requested. Basically you treat the lists as a wishlist rather than a requirements list. Maybe you come clean later once they like the prototype.
I'm not saying it would have saved the project, I'm just saying it's better than giving up and saying "the project is doomed" like OP did. But maybe OP wasn't cut out for a leadership role.