Not a lawyer, but in German labor law an agreement to hire usually already constitutes a contract that you can't just cancel - they should have probably paid a lot more to get out of this!