It still sounds odd, at least to my ears.
It's probably a case of the difference between spoken and written English. Native speakers will begin a sentence not knowing how it will end, or end a sentence unable to remember how it began (anyone who has ever lost the thread of what they were saying in mid-sentence will know this); indeed, it has been suggested (and research seems to support this) that the basic unit of speech is not the sentence, but the phrase or possibly the clause.
If we take Tdol's "utterance" (we can probably call it that, since writing in a forum like this is half-way between written and spoken English):
"I've already told you [...] when you first brought it up."
It looks like a sentence, but actually it's a series of loosely-connected phrases. Writing as he thought, he began with a present perfect, intending to emphasise a present state of affairs ("You are in possession of the relevant information"), which normally precludes the use of a past time adjunct. By the time he got to the end of the sentence, however, this initial focus was forgotten, and, moving on, he added some extra information about the time he claims he told you.
That this is happening may be hinted at if we examine a much shorter sentence, like:
"She's left yesterday."
That sounds even less natural.
This is to say, in Tdol's sentence, the past time adjunct is more of an afterthought, and not actually connected to the verb except incidentally.
It will be interesting to see how the past simple/present perfect divide continues to evolve. In German, which used to have exactly the same division between past (event in the past) and present perfect (present result of a past action), the present perfect has now lost the idea of a connection with the present and is almost interchangeable with the past, the difference being one of style (the past being the more formal variant).
Already, there is a divergence between British and American usage, the past simple being preferred in the US. Will the present perfect die out altogether? Or will we go the same way as German? Only time will tell.