deleting locations from map
No need to delete the app :) To clear your search history, go to (from the Home screen) Menu > Settings > Applications > Manage Applications then hit Menu again and choose then hit Menu again and choose 'Filters'. Choose 'all', and then scroll through the list to find 'Maps'. Select that, and then on the next screen press 'Clear data' and confirm.* through the list to find 'Maps'. Select that, and then on the next screen press'Clear data' and confirm.
Deleting recent destinations
On my Motorola Droid I did the following . I went to Setting , Applications , Manage Applications, scrolled down to Maps and uninstall update.
This cleared out the recent destinations. BUT you must reinstall updates to maps to get back to what you had.