Generally the response is to drop a few hundred on a lawyer to write them a stern letter about bad faith and failure to execute the contract. Your specific legal remedies vary so much country to country that it's hard to generalize, but I have been shocked by how quickly nonsense becomes sense when formal letters requesting negotiation and arbitration enter the scene.

A labor lawyer generally knows what regulatory remedies exist and can send the letter in a way that it gets attention outside of the HR or and Hiring managers desk.