Your question refers to the problem of "alloreactivity of lymphocytes".
There are several related questions on stackexchange, and there is plethora of literature, some call it puzzle, enigma; your question is valid.
You emphasize twice that MHCs of host and graft are different whereas antigens are identical (as graft and host are no different species):
"Human tissue is essentially similar between individuals. (...) the only cellular membrane protein that is (almost) unique is the major histocompatibility complex (...). And: "OK so NKC spew out the remains of alien tissue cells, but these residues are surely very similar to any other self cells' internals?" (only in your comments you mention that non self MHC as a "surely not similar" antigen may be presented on self MHC (which it is is fact, by the way))
What is the implication of antigens, contrary to MHC, being the same?
That there has been undergone a process of tolerization, of sorting out, of "negative selection" of T- and B-cells that are specific for that same antigen of host and graft.
Quote: "My understanding is that recognition can only be achieved when the antigen is presented on self MHC type I protein. (...) This difficulty (perhaps my understanding) is at the heart of my question. (...) NKCs will do the job of course!"
I believe what you imply is that any T cell that might attack its specific antigen on non self MHC would have been sorted out by negative selection: no one left to present the antigen to on self MHC, the ones have been departed or gone.
How can any T cell escape "negative selection" if it is specific to the same, identical antigen which after transplantation is presented on foreign or self cell, be it by APC cell or tissue cell. Any T cell specific for that antigen should have received a "death signal" and not exist any more. I think that is "at the heart" of your question.
Can "cross reactivity" (see literature) solve the problem? This is difficult to see if you have that paradox of "sorted out" in your mind. There seems no T cell "left " to attribute that quality to.
However, there is "tolerance". Any basic textbook will not elaborate on Lymphocytes specific for the antigen being NOT sorted out. They do exist. In "negative selection" only lymphcytes that bind too strongly receive a death signal, there does exist a set of T cells specific for that antigen that are "tolerant", weakly binding, and escape to the periphery. I think it is a possibility that they act "crossreactively" when that same antigen is being presented on foreign MHC (as they may bind "strongly" to foreign MHC, to explain: if they had been negatively selected by foreign MHC they would have been sorted out as "too aggressive", assuming they bind strongly to foreign, allo-MHC, weakly to self, iso-MHC), and, when being activated by APCs presenting that antigen, which might be host or graft MHC.
So I will carefully reread my textbooks, and these are a few learner's hints added: in positive selection, there is "already" specific peptide, antigen, being presented. If you see the antigen in positive selection that is not a process of killing any cell that does not bind to self MHC, in other words their might be a set of lymphocytes that do not bind strongly enough "in the first place" and do not enter positive selection as they "only" bind graft MHC. Second hint: the death signal in negative selection goes to the self MHC binding cell (just the opposite). The set described above leaving negative selection may very well be the one which is said to be "cross-reactive" in literature).
The gist: First, it is not true that there is "positive selection" that does not present (self) antigen. Thus, it is not true that in positive selection all lymphocytes that do not bind self MHC are sorted out and eliminated. "They came for the antigen", that is my hint.
Second, refering to negative selection: it is not true that any lymphocyte is sorted out that binds to self antigen. The ones that might bind that specific antigen but do not bind too strongly, do not become aggressive with "their" self MHC "leave laughing". Logically, they might bind strongly with that specific antigen plus NON-self MHC. Non-binding strongly with antigen plus self-MHC does not imply non-binding with transplant-MHC plus antigen.
Hint: it took me a long time to put it that easy.