I am having the same issue with my AW5. I have all recents deleted on both my phone and IPad. I have unpaired and paired the watch. Erased and deleted AW5. Removed the Maps app from both iPhone and IPad and reinstalled. Turned off Maps in iCloud and turned back on again. Nothing has worked. The same two ”Recent Searches” remain on the AW5 despite nothing showing in this field on the IPhone and IPad.
What’s odd, is that I can do a search for a restaurant for example, on any of the devices, and this search will show up as expected under recents on all devices. When I delete this new search, say on on my Iphone, it will be deleted on the AW5 as well, but the same two stubborn “original” searches remain. I contacted Apple technical support, and they were stumped. Still have an open ticket for the issue...