Posting in case this helps anyone else.
One can obtain a "NO ENTRY" Certificate from "Baldia Uzma Karachi" (Karachi Metropolitan Corporation/KMC). This is a three page document that is usually as follows:
Page 1 - actual "NO ENTRY" certificate, that states that the details from page 2 were searched for, and were not found.
Page 2 - details of the applicant (this looks like a birth certificate, has name/date of birth/parent's info, etc.)
Page 3 - affidavit for page 2 stating these are the facts of the matter.
Contrary to what others have said, and often say, this can be obtained by normal people. One does NOT need to be a lawyer or agent to get this document.