It depends on the developers and how they implemented the quests. Some you may have to do over, others will know you've done them. I feel your pain on Give Up, just played it through last night.
I decided to refresh my gaming experience for Kingdom Rush and at the same time, try to add some quests to my list for this game. Turns out those I already achieved were actually given to me when I played through the first level again!
Sometimes it can help to play a level of a certain game and when finishing it, the game recognizes your account and updates the quests. This has happened to me for Kingdom Rush. I already achieved 3 quests while playing it in the past and they were rewarded to me after playing the first level again to get back into the feel of things.