I’ve just got an advice on Twitter from Daniel Střelec to simply use sanitize_title – which is a better solution anyway, as it removes whitespace and other non-ideal characters for filename. Use it this way:

add_filter('sanitize_file_name', 'sanitize_title');

I’m keeping the question opened though, as what I’ve described above sounds like a WP bug to me.

Edit (important!)

Do not use sanitize_title for this purpose! It does remove accents, however it replaces dots with dashes which invalidates image URLs.

image.jpg => image-jpg

This is my current implementation:

add_filter('sanitize_file_name', function($file_name_full) {
    $file_info = pathinfo($file_name_full);

    $file_name = sanitize_title($file_info['filename']);
    $file_ext = $file_info['extension'];

    $result = "${file_name}.${file_ext}";
    return $result;
}, 11);

Also – pathinfo($filepath)['filename'] is supported since PHP 5.2.0, so watch out for that (but you should use current version of PHP anyway).