Well, it depends how paranoid you are. Sites could still store history even if they say they don't. Like how people realized Facebook wasn't truly deleting your account when you asked for it.
But you make a good point about making search results worse. That's a real risk. It's the classic convenience vs. security/privacy trade off.