Yes, it needs to “respawn” or something, but if you come back in say, 12 hours because you forgot what time you did the champ last it will show a skull. Come back an hour later. Come back 15 minutes later and it will show the skull. Just not right away after killing it.
I can say that for myself, as much as about 12 hours later, skulls have not been showing for me when they are on cooldown. This includes things like BF where it is an interact-able object that shows the skull. Not sure why it is showing the skull for you or any others who are seeing it.
I’ve not seen map markers for champions on cooldown, either. But if anyone does, that’s clearly a bug. Although I wouldn’t expect a fix before year’s end with most of Funcom out of the office.
Meanwhile, might I suggest the low-tech approach of writing down the zone name and kill time on a piece of paper (alternatively, notepad.exe if pen and paper are not readily available)? It’s a remarkably reliable method of tracking cooldowns that has served me well for TSW’s golems in years past. 
Quoting Dame Julia : “when I was a field operative, I kept my journal in an actual journal.”
Anyway, I still expect that if I can start a mission, I can go and complete it “now”. Clearly, this isn’t the case with this mission all the time. Instead it’s sometimes “come back in two hours”.
An easy fix would be lowering the amount of champion kills from 4 to 3, but I read elsewhere that people have problems getting their phones even with 4. So that solution might be just another can of worms opened.
Today I didn’t get phone from first 4 champions in the morning (killed backup champ in CF and got phone from him). And in evening I got phone only on 4th champion.
This is super confusing and somewhat broken.
I did the 2nd quest 2.5 days ago, killed 4 of the champions… A day later, quest still on cooldown, I was questing, and one of the champions I killed the day before was up again. I killed him and got loot. Yesterday, he was up again… killed him again, got loot.
Today the quest reset for me (I’m not a patron), I went back to the champions I killed 3 days ago, and one of them wasn’t showing (I haven’t killed him since), yet the one I killed yesterday was up again?
Which zone wasn’t showing? Some move, and it’s possible someone had just killed the one you were looking for if you didn’t wait a few minutes or come back again.