So, some 10 turns or so after I killed the monster from the deep and gotten the reward for it and completed the quest, a new one appeared. This time without giving me a quest to kill it (presumably because i had already finished that quest already)

I am guessing an AI triggered the quest and I coudn't receive it since it was already completed for me

note that the new one that appeared had a slightly different set of minions and started out at a lower level again.