You have to go to their website on a physical computer, log in, then you can delete everything. However, it does NOT clear the list when you are on the Layers menu. Maybe clearing cache does that. To solve it for the most part (for whatever reason, things still show on the layers menu), I set it not to save my history. The tracking of where I'd been each day, while interesting, was kinda creepy. You could possibly log out as well (from Google Play) then there wouldn't be an account to save anything to. Haven't tried this approach though.
Oh, if you just have coordinates on your map searches, checking to see what it was just adds it back to the list at the top of the history.
Sent from my totally awesome Sprint Galaxy Nexus, even if I don't know all its secrets yet.