1) It is most likely your specialized theme and CSS that has rendered the search by category as an issue, use the debugger or switch to a plain WP theme on your staging test site and see if your search works the way you expect it to.
Do not do updates on anything other than a Test or dev site.
See Updates Search not working
2) If you are reporting that you removed categories from your admin area of site but still see them on front page, that is a different issue since Category tables taxonomy is a WP dataset
I am not quite sure what the real question is since your site instructions and what to do first second third is a bit confusing for me. Such as wait for map to load select town first or category or..it seems you have quite a few specific layouts and may be worthwhile to ask your developer about what may have changed on your end
The taxonomy and changes are mentioned in the WP 5.7 changelog. So if your dev team had added
https://developer.wordpress.org/reference/functions/get_taxonomy_labels/https://developer.wordpress.org/reference/