Not the hosting company, I don’t think they can do anything about this.
This must be caused by either a modification in the .htaccess file, a custom code snippet or a plugin, or maybe even a theme option somewhere – this is not normal WordPress feature.
– If you have added any custom code snippets recently, check those first
– If no luck, try looking up the theme settings, specifically around search features. If there is any option related to that, it should be something like “search permalink structure” or “custom search permalink” or “seo friendly search url” – something like that. I have seen that in a theme before, so it’s a possible cause.
– If still no luck, try switching the theme first, to see if that changes anything.