I'd be interested to know where you are (geographically) or your users at least.
When I mouse over the one that gets 404, then where it actually looks like the 'R%E5dsm', the %E5 becomes a lowercase 'a' with a small circle over the top ie a-circle
https://en.wikipedia.org/wiki/Diacritic
See
http://tlt.its.psu.edu/suggestions/i...ge/nordic.html for details ...
In other words, its a locale issue.
You need to decide how you want to handle this eg make whichever Scandinavian locale your locale in mailscanner/apache, or use a translation table/regex to reduce to std English 26 char alphabet.
To reduce, I would probably use Perl, which has a very powerful regex engine.
HTH