Health plan wishes to tell third party (for other than TPO purposes) that individuals X, Y, and Z are not and never were enrolled in the plan. Health plan has no connection whatsoever with the individuals. I know that information that an individual is enrolled in a plan is PHI, but is information that a person was never enrolled also PHI, subject to HIPAA? For example, if the health plan discloses to a third party that Donald Trump is not and never was a participant in the Plan, has the plan violated HIPAA?

PHI is PHI, whether enrolled in a health plan or not. I am not sure what the group is trying to do, but it sounds like the group is trying to communicate that 3 individuals are not eligible for their health plan and that these 3 individuals have never been on the health plan, is that true? If that is the case, why not just send the eligible list the tpa and they can use that.

But is the existence of insurance coverage really PHI? I've had the understanding that it's not.

http://www.hhs.gov/ocr/privacysummary.pdf
“Individually identifiable health information” is information, including demographic data, that relates to:
• the individual’s past, present or future physical or mental health or condition,
• the provision of health care to the individual, or
• the past, present, or future payment for the provision of health care to the individual, and that identifies the individual or for which there is a reasonable basis to believe can be used to identify the individual.

Existence of coverage does not give any indication to: physical condition, the actual provision of health care, or payment of claims for actual provision of health care.

As I understand it, the third party requesting the information is involved in potential litigation possibly involving the three individuals (that is, if they participated in the plan). The plan wants to inform the third party that the three are not participants to put the matter to bed from the plan's perspective. One solution is to just inform the third party of the eligibility requirements for plan participation (e.g., from which the third party can determine that Donald Trump is not eligible) but I am trying to determine whether telling the third party straight out is okay.

I am not a lawyer, and I don't play one on a tv show, but it seems to me that this should be done through their attorney. Remember something about PHI, just because the information is PHI, does not mean you cannot disclose that information. It just needs to be disclosed as described in the law. Again, since this involves potential litigation, you should let the attorney's handle this.

You are correct, the existence of insurance coverage is not PHI. Some of the information contained within that coverage (medical condition, name, etc.) is the PHI.

My understanding is that enrollment/disenrollment information were never excluded from the definition of PHI; just that if an employer holds this information in its capacity as employer it is not PHI.

The present matter involves a multiemployer plan. Multiemployer plans do not generally have employment functions, so I think it is difficult for their enrollment information not to be PHI. The plan does not disclose whether an individual is a participant in the plan unless the disclosure otherwise complies with HIPAA.