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.