This is the answer I got when I posted the same question on the AHIMA website.
I tend to agree with the responses I received here on the AAPC threads, but the AHIMA response reopens the question.
A Definition of New Patient for Selection of E/M Visit Code
Interpret the phrase “new patient” to mean a patient who has not received any professional services, i.e., E/M service or other face-to-face service (e.g., surgical procedure) from the physician or physician group practice (same physician specialty) within the previous 3 years. For example, if a professional component of a previous procedure is billed in a 3 year time period, e.g., a lab interpretation is billed and no E/M service or other face-to-face service with the patient is performed, then this patient remains a new patient for the initial visit. An interpretation of a diagnostic test, reading an x-ray or EKG etc., in the absence of an E/M service or other face-to-face service with the patient does not affect the designation of a new patient.
The patient is still new if no seprately reportable E&M service was performed.