Dear fellow Droids,
I had been having this problem for about 2 months

and today I managed to clear the Android Market Search history

.
settings> applications > manage applications > CLICK Market,
Here I tried but could not 'clear cache' because it was already empty

, so I reckoned that I probably should try the 'clear data' instead.
NOTE. For the record, I also tried going to 'settings> applications > manage applications >Internet' to clear cache but when that did not work
, I went back to 'settings> applications > manage applications >Market', and when I checked again in the Android Market, it prompted me to 'Accept' and once inside market, I found that the Android Market search history was gone
.
Best regards,
Azul