I've just had an idea.
One of the "problems" cited for "replaceable" fair-use images is that they give the (false) impression that an image is no longer needed for the relevant article, right?
Well, maybe it would make sense to mark nonfree images in the article somehow. A red border, perhaps.
I know the following suggestion requires extra coding, but I imagine it would be possible to have a tag on the image description page (which, in the case of the English Wikipedia, would be transcluded through some of the copyright-status templates), which would cause the image thumbnails in articles to have an extra CSS class specifier. Then extra styling can be added for that CSS class specifier, e.g. red border or background. Or it can be neutral by default but still enable CSS wizards to add something to their own user CSS.
Discuss. :)
Timwi