The permalink to the entry detail page is not really a search result… the entries themselves are the search results.
Sorry, but there is no way to alter the entry’s permalink structure. Even it could (well, it could if all the rewrite rules were completely rewritten and then all the supporting code changed to work with the new rules) the permalink structure you want would not work. First, the example would lead to a list of results and the the entry details. But more importantly the WordPress Rewrite API does not support a structure like that. The closest would be this (a working permalink, give it a try):
The way it works, you need a “key”, example “region” followed by a value, for example “UT”.
I suppose technically the locality permalink should be like the example permalink I just gave, but changing it would not provide any additional results:
As you see they are the same.
Apologies, I know, not the answer you were hoping for.