I discovered this behaviour while dealing with a file named 'Abiturprüfung.xlsx' which obviously contains the German umlaut ü. To reproduce simply upload the file attached to a moodle site as file into your test course or wherever. Save and afterwards try to download the file. Moodle raises a file not found error.

I found out that moodle calculates the pathnamehash on upload in a different way than on download. In the first case it uses the filename to build the string for SHA1 calculation whereas in the latter case it first urlencodes the filename which leads to a nonsense SHA1 hash and result in failure to find the files entry in the database. In line with this you can fix moodle to find the file by building the pathnamehash including the urlencoded filename Abiturpr%C3%BCfung.xlsx

I found an unanswered thread where it is stated that the false hash might be a result of migrating a moodle instance from linux to windows. In our case no such migration took place. The system is linux only and the file was just uploaded. Nevertheless the thread must be addressing the same issue we just experienced. The poster also presents a one-line patch that solved their and our problem. Maybe it could just be merged into the moodle code though i can't estimate if it breaks anything else. Look here: https://moodle.org/mod/forum/discuss.php?d=233863