This is not a matter of change request best practices, but a matter of contract negotiation and relationship with the customer. There is a reason why fixed-price contracts for developing software are just a ticking bomb waiting to explode; read for example Is Fixed-Price Software Development Unethical?
There are a few things in the question that I want to comment on
usual question about change requests management.
There is a lot of literature on how to handle change management with best practices already, but like I mentioned, the issue is not this. Any changes to the scope, and how you handle them, need to be agreed and accepted by both parties involved. In your question you point out to a disagreement. This needs to be solved with the client, not with a process for managing changes. When you and the client will be willing to agree on how to handle things, only then will you be able to lay down a process for managing change. When contracts sit between you and your client, the discussion will revolve around who said what in the contract and who is at fault, instead of finding ways to collaborate.
After 6 months we are of course behind of schedule
Wrong. Saying this is like saying "the schedule was correct to start with and we are doing something wrong now". It's the other way around. The schedule was wrong and reality is now pointing that out. You can't know on some day what the next 12 months will be like. That's simply not possible.
One of the reason is that after initial requirements grooming, at the requirements signoff stage or even when the feature is done, the client ask for improvement.
This is another reality of software development. The client always changes their mind. They don't know what they want in day one, so laying down complete upfront requirements is impossible. Even if this is a rewrite or a redo-over of an existing software which contains the full functionality that's needed, if the client wants a new software solution based on the existing one, then obviously the existing one is lacking in some way. So you are back to the client not knowing upfront what they want and asking for changes once they see the software or think more deeply about it.
To catch the schedule we decided to not allow any changes.
As I just mentioned, clients don't know what they want. So the notion of fixed scope doesn't really exist for larger projects, no matter what contract you signed and what schedule you agreed upon. If the client wants changes, then it means they have realized that they need different features to satisfy their needs. If you don't allow the changes, you are forcing the client to accept the initial scope, which - in retrospect - doesn't look like the one that's needed.
You did not do proper analysis of the existing system, so it's your fault
This is true, but it isn't the whole truth. Yes, building on what I said above, you did not do a proper analysis of the existing system. But your client is at fault too for assuming that you did so in the first place. Six months into the project it's now something obvious to point out, but seriously, did they really think you got it right from the start? Fixed-price contracts are a way to throw risk around. Clients put all the risk on the IT provider. No matter what happens, they pay a fixed price and the provider should manage. So that's why you need to spend a lot of effort initially, to agree on requirements and put a price on the contract that covers the cost of the build, any potential risk, plus making a profit.
If this is a substantial change let's trade for some other feature.
If you don't have a bullet proof contract, then they could just as well argue that something isn't a change, but a bug, or maybe a misunderstanding on your part. So it's a matter of what's written in the contract and how it's written. At least the client is willing to get one feature instead of another.
It's not possible to do 100% requirements discovery and it's important that the system fulfills user needs and not mimic the old one
Correct and correct. So you have to find an agreement to make things work for everyone. A new contract or a renegotiation of the existing one might be needed.
Trading is not an option for us since it requires impact analysis anyway and will drag resources from working on the project to catch up the schedule
If you really want to build the right solution for the client, then you have to do this trade-off. There is an extra effort involved when things change, that's just how it is. Again, you have to find an agreement to make things work for everyone.
those are not good enough explanations to the client and they insist on changes.
Yes, because they don't want some software, they want software that fills their needs. The fact that you agreed on a different solution in the beginning is sadly irrelevant. It's simply a reality of software development. When this happens, parties either find a way to collaborate and agree on something mutually beneficial, or they bring out the contract and the lawyers, start finger pointing and blaming, and invoking any clauses or penalties from the contract.
Any ideas on how find common ground here?
Any changes in fixed-price contract need to be payed separately. Your contract needs to be very clear what a change constitutes and how these changes are managed an paid for. So what's written in the contract is what you will work with. But flashing contracts in people's faces and sticking to them when you know one party is loosing isn't the best solution. You need to have collaboration.
If the current situation isn't working out, sit down with the client and agree on a new way of collaborating, on a new contract, or on new terms of the contract. Maybe you deliver what you have built until now, and terminate the fixed price contract (again, the terms of the contract are important for how you terminate it; there might be cancellation fees, etc) then move to a more Agile approach with time and materials contracts for example. Fighting over terms of a fixed-term contract is usually a lose-lose situation.