One tidbit I picked up along the way yesterday is that Cortana stores information in the "cloud" as well as in the regular search history. Consequently if one wants to clear one's search history in Cortana one has to not only clear one's regular search history, but one also has to delete what Cortana has stored in the "cloud" (whatever that is.)