Redirects to addresses with random prefixes. How to fight?

Question

IIS

I ran into a mysterious problem: when I visit my site, with some probability, I get a redirect to an address that consists of the source address with a prefix in the form of one or more segments of the form /\w{4}Z/(XlpYZ, LhdkZ, etc.) going to the address /some/address/ I get to /LhdkZ/some/address/
The logs contain entries about hitting similar addresses with different user agents and from different sources (from search engine results, from the site itself or direct visits). IIS web server. There is reason to believe that redirects are performed even before the request hits the web server.