The short answer...yes. Unfortunately the Carbonite history database will only automatically remove those parchment icons for quests you've completed since installing Carbonite. This is not something the Authors can code in to mark those quests you completed prior to installing Carbonite.
This is not a limitation built in by Carbonite, it is a limitation imposed by Blizzard as there is no way at current that Blizz allows us to see our quest histories without some form of addon tracking all the quest's we've completed.
On a side note to the above....If you only want to see the icons for daily quests on your maps, try playing with the radio buttons in the Quest Tracker. I cant remember the color of the button, but one of them toggles through the options of what to show.
Hope that helps