Your store keeps track of what language/region is active with a small code in the URL. For example, on my test store of https://hextomhenrytest.myshopify.com/ if we change the language to German in the US market, we will be on https://hextomhenrytest.myshopify.com/de-us. The "de" denotes the German language, and the "us" denoted the US market region.
This means that for the links on your store page to work correctly, they need to include this information. If we are on https://hextomhenrytest.myshopify.com/de-us and create a link to the search page by linking to https://hextomhenrytest.myshopify.com/search we would go to the English page. We need to link to https://hextomhenrytest.myshopify.com/de-us/search to keep the same language and Market/Region.
Links set up through Shopify will do this automatically, but if you have customized your theme then you might have links that are "hard coded" and do not include the language/region information. The best people to assist you with this would be Shopify support, or your theme support, but if they are not able to assist you then please let us know at email@example.com what links have this problem and we will be happy to assist you ourselves!