Deemed rehabilitation is for those with charges taken place after 5 years but before 10 years. This process can take up to 5 months. After 10 years, I'm not sure. If the paperwork is all in order it probably just get's done within your application time-frame - but I don't know this for a fact.
Your best option is to have the police, government or other organisation involved to write a statement stating nothing on file after this time and the case was dealt with by mediation. If that's not possible you will need to submit a letter from a lawyer outlining why nothing is on file and that all the information available has been submitted.
In my case the transcript made by the courts of what the judge said is no longer available and was available only as audio. Minor cases audio trans scripts are kept for only 5 years and then destroyed. I asked for a email or letter stating this for immigration purposes and they obliged.
If all else fails you will have to submit a letter on your own saying you have done everything possible but without legal backup of a lawyer, police or judge it will not be as strong and they may ask you to go back and get a letter. OR they might accept it since it was 18 years ago. Have you emailed them as well to outline everything you've done, they might email back with another option?
