[KevinH]

Not seeing any of those issues on my machine. Nothing has changed in search in the last couple of releases. Please note that the Wrap checkbox only has any meaning when searching in the "Current File" mode. When searching across multiple files the state of the search is kept so that you visit all matches just once. You can override that by changing any of the search parameters (which starts a new search) or manually hitting the restart search button.

Changing the ncx or regenerating it should have no impact on search or search order.