In the case of a patient who refused an exam, or it was (allegedly) not performed, I always ask two questions:
1) Were any vitals taken and if so, did the doctor review them?
2) Is there any documentation of the patient's general appearance or some type of observation of the patient noted by the doctor?
If the answer to either question is yes, then there IS an exam as this would be the constitutional element and voila! You have a problem focused exam. Not much, of course, but there is at least something that is documented and is part of the exam element. Means that for a new patient, you would have to code 99201, but it is better than nothing.