The issue was awfully hard to debug, but in the end, the solution is easy.
The links for the sorting are inserted in an escaped manner into the page. Example:
When the select element is changed, the function
js/varien/js.js is called. It basically simply does a
`window.location.href = url;`
Unfortunately, since Magento 184.108.40.206, the implementation has been extended with an
`window.location.href = encodeURI(url);`
This means that these links are encoded twice. Once when inserted into the page (mind the
%C3%BC in the option value above) and once when switching the location. Then, the param
% is encoded with
%25) is sent to the server, so that the request fails.
My solution was to override the template
app/design/frontend/rwd/default/template/catalog/product/list/toolbar.phtml and change the following call:
Not sure if this is the most elegant or most secure solution, but it works at least ;-)