In that case there might have been something else overriding the results (or perhaps modifying them in some way), I'm guessing by turning on the override option on the search fixes that as it passes the objects correctly. Anyways, it is fixed and that's great.
Changing the links on the results page very much depends on how the theme outputs them, and unfortunately there is a good chance that they might not be changeable with the standard known methods, I'm not sure to be honest.
I've taken a sample solution from the wordpress documentation, which should work in most cases for changing the permalinks on the results page:
Again, this very much depends on the theme itself, but it's worth a try.Best,
If you like my products, don't forget to rate them on codecanyon :)