We had the same issue several weeks ago, and resolved it by rebuilding the search index. I also enabled the ShowRebuildSearchIndexButtonToAdmins key in our user.config, so that if this happens again our webmaster can easily rebuild the search index herself.
I've been keeping an eye on it, but so far there hasn't been a recurrence of the duplicated search results. I'm not sure what caused it--this is probably one of those nagging type bugs that are extremely difficult to diagnose.