OK, so that seems to indicated that it's not really a problem with IE; it's something related to your normal user account. And if I were a betting man, I'd bet on GDS.
First, make sure that you've updated to the most recent version of GDS. If using the most recent version doesn't cure it, somewhere there's an option for GDS to index IE's history files - disable that option & see if it cures the problem.
As a side note for my own information, is there something about GDS that you prefer over the search function already built-in to Vista?