@ Richard
It appears you may have changed the page hierarchy which no longer reflect the current Google index. As Google updates its index those links will be updated to be correct.
That said… you really should reconsider the structure of all these searches… each one should resolve to a canonical directory. Choose a single page to embed your directory on, then use either the force_home or home_id shortcode options so all links will resolve to that single directory instance.
For the “category” searches you should build the links so the resolve to the canonical directory. An example link would be: https://infoshield.co.uk/simple-search/cat/auctioneers/
Using such a link will use the internal Connections permalinks to filter by category.
Hope this helps!