Hi, I cleared the search history by going to settings --> applications --> manage applications --> all --> Market and selected "clear data". Got a warning that all info would be deleted. Logged back into market and had to re-accept the terms and conditions. Search history was cleared. Went to the download tab and all the apps I have downloaded in the past are still there.