I just used the "File Manager- Apps Manager" selected Market, Uninstalled. It's in the firmware so it can't actually uninstall, it just resets the market, and History is gone.
Note This was on my Android Samsung captivate, YMMV
Learned Via this thread
http://www.google.com/support/forum/p/Android+Market/thread?tid=079975a56ae55776&hl=en