Most recently this happened to me when I had to fetch sand from the sand golem.  I entered the sand golem square and was given the prompt whether to fight or not.  I chose fight.  I was then back at the strategic map.  The special square was gone, but the quest had not updated.  I still needed to find the sand golem, but it was no longer available.

The problem happens on other quests as well though.  I have had basically the same thing happen--necessary goal removed before updating the quest--while gathering herbs, defeating bandits, fighting darklings, and exploring a bear cave.  I would say it happens about a third of the time.