How to clear search history in Apple Maps
Looks like you have iCloud enabled, and it keeps putting the removed entries back 


Settings app  
Select your Apple ID  
Tap iCloud  
Scroll down to Maps 
Toggle it off  


Then go back to Maps and swipe to delete.