Cohen or Kohein?

A certain young man returned to the faith of his fathers. As he learned more he adjusted his behavior to comply with his new understanding. Although this baal teshuvah’s last name was Cohen and he had always assumed he was actually a kohein, after he heard a shiur on the subject he was no longer so certain. He had heard that his paternal grandfather had married a non-Jewess. Not only that, but family rumor had it that this woman remained a practicing non-Jew for her entire life and was buried in a non-Jewish cemetery. According to the shiur that he had just heard then, he was no kohein at all. When he broached this subject with his rabbi, the rabbi ruled that he is not a kohein in any regard and may even marry a divorcee.
But when he told this to someone else, it got even more confusing: “How could your rabbi say this? Who told him that we trust your family rumors? There are halachos that determine who is acceptable for bearing witness. When we believe things or not is a complicated matter…”
This second person consulted with Rav Shmuel Wosner, shlit”a, regarding whether or not the first rabbi consulted was correct, and if not whether they should protest the psak. Rav Wosner answered, “It is well known that there is a dispute about how we are meant to understand the gemara in Kiddushin 69. The gemara tells us that Nechemiah refused to give kodshei kodoshim to the children of kohanim who could not procure documents proving their lineage. Some authorities learn from here that since our kohanim do not have such proof of their heritage they are all questionable kohanim. Other authorities counter that they were kosher for avodah, but Nechemiah had more established kohanim available so he disqualified them. According to this view, had there been no other kohanim to perform the avodah they would have been valid. In our case, although we cannot be sure of this young man’s true situation, it would appear as though we should believe what this young man heard. This is especially true since he may be able to track down his grandmother’s grave in the non-Jewish cemetery…”
Rav Wosner concluded, “G-d forbid that we should be lenient in other cases, but if someone rules in this case that he should not be treated as a kohein, we should not reject that rabbi’s ruling. As for the name Cohen, this is irrelevant to his status. While it is true that he has a chazakah in his name, he does not have one in his kehunah!”