He then tried to upload his improved version of the image.
[..]
Long-term solution: Replacing the image should be transparent. He should not have to care where it is hosted, it should just be replaced wherever it is.
Apart from the valid points, I believe this is a fringe case. The case in which you should upload over existing images are few. The alternative of uploading with a new filename doesn't seem so counterintuitive to me that it should deterr a lot of contributors. But I could be wrong here.