What to do when exception is thrown after state is modified?

In our system the user makes an order, which is a synchronous REST POST method call. The service then modifies the state of the system.

Now we are struggling with what to do if the service modifies the state, but fails in the end, eg. due to system shutdown?

In a asynchronous approach it would be pretty straightforward - the message from the queue would not be processed so it would be retried.

However in a synchronous approach the client already got 500 error. He may never retry the action.

The only idea we have come up with is to have a background job doing the necessary cleanup (seems like implementing eventual consistency). What is the correct way to do that?

---

NOTE:

This might apply to any system, but in our case the "state modification" is actually a complex operation across multiple microservices using the saga pattern, which needs to be rolled back if something fails