What were the consequences in the document for failure to comply? If they are not spelled out explicitly in the document then even if it is legally binding there are not consequences for failure to comply. Its possible a judge could order you to comply or face contempt but I find that highly unlikely, as the costs of pursuing you in court over not sharing are going to be prohibitive.
Most likely the consequence will be that you are not eligible to be rehired. It is possible that the penalties will be be spelled out, if so then take your copy of that document to a lawyer and get their opinion on the legality of it. Many times these are still not enforceable.
Some ways you could get around this would be if you inform them that you intend to pursue freelance work, take some time to off to find yourself, or something else cliche that does not provide them with anything they can bargain against, or create problems for you. Then after you depart the company and start your new job, if necessary by the contract, you can inform them that you have accepted a position with the company. I would probably let your new employer know you have to do this, and wait for a few weeks or even a month before sending the letter. I would only do this if you are required to notify them in writing. Once you have been processed out and they have moved on there no reason for them to try and cause problems with your new position.
If you are not required to notify them in writing, it is your word against theirs whether or not you provided that notification. That will not stand up in court should they bring a case against you since the company will have to prove that you failed to comply, if simply telling them the name of the company verbally fulfills the contract they will not win should they try.