Just for those, who don't already know:
Delete /data/data/com.android.vending/databases/suggestions.db and the history is... history.
Cause the list of things you search for in the market can get out of hand, and theres no real way to delete it. Cachemate will do it automatically for you if you set it up to. Thanks for the info though, jdx.