But that expresses a link with the present, whereas the perfective is a one-time completed action. 'Didn't recieve' sort of 'nips it in the bud'. Maybe 'has not recieved' would be translated у него всё ещё нет твоего письма :S Or maybe, I'm talking crap and it should still be correct haha
Still the perfect tense was not accepted, contrary to what says here.
I'm afraid I cannot give you a clear explanation apart from saying that this is the way Russian language works, as you touched one of the most complicated issues of Russian grammar. But to shed some light on the issue, I'll refer to the most authoritative source of information on Russian grammar, the guidebook written by D.E.Rosentahl et al. - http://www.evartist.narod.ru/text1/66.htm. Section 201 of the book entitled "The case of objects of transitive negative verbs" explaines that objects of transitive verbs preceded by the negative particle "не" are usually put in the genitive case to emphasize the negation in a number of contexts. For example (see item 4 of Section 201), the genitive case is preferable when we are dealing with an object of one of the verbs иметь, получать, доставать etc. which,, if used with "не", do not express full negation - не имеет комнаты, не получил приказа, не достал билета, не приобрел нужных вещей. The difference between Он не получил твоего письма and Он не получал твоего письма is that that the former statement denies the expected act of receiving the letter, whereas the latter is more appropriate as a somewhat emotional response to blaming the adressee (Don't blame him - he never got your letter. The translation suggested by DL sounds a bit substandard to me (a bit like saying "It ain't nothin' to do with me'), although these days it is widely used in a casual conversation.
Since you are sensitive to issues of style, I thought you might like to know that "I did not get a letter" being instead of "I did not receive a letter" produces similar discomfort in me. Of course, there is no circumstance when receiving something does not mean that you got it, but to use "get" when "receive" is meant is rather low style.
I got a letter is appropriate when you mean that you went somewhere and collected a letter (e.g. from a post office); if it was not your activity (it simply arrived through your letterbox), it is better to say * I received a letter*.
Do either of the alternatives you gave cover the former sense of "getting a letter"? (my understanding is that they do not, but I would like to be sure)
I don't if this will help, but, in Russian, you can say, "Он не ходил на почту за твоим письмом" and "Он не удосужился сходить на почту за твоим письмом", the latter meaning "didn't bother to go". Получил means 'received', it doesn't imply any efforts to get the letter. On the other hand, if the letter slid behind the couch and someone tried to get it out but failed, the translation of "He didn't get your letter" will be "Он не достал твоё письмо".
I doubt that "He has not received his own letter" can also be right unless he wrote the letter to himself like in the famous song beautifully sung by Paul McCartney: "I'm gonna sit right down and write myself a letter / And make believe it came from you." (The album is frivolously called "Kisses on the Bottom", and its title is a phrase from that song).