1) Brion is on the case already. There's a code change in CVS that will allow InterWiki redirects to show a "Redirected from" like regular redirects.
2) Angela pointed out to me that even if the image was deleted from the English Wikipedia, it could still be on any of the other wikis on the InterWiki map (e.g. all Wikicities), all of which can be used for InterWiki redirects. So you wouldn't just need a cross-Wikipedia deletion or linking policy, but pretty much one across all wikis. That is clearly not a workable solution.
3) The autofellatio image may be a case where many people agree that it is inappropriate in any context, but many images which we clearly want, such as the photos GerardM uploaded of venereal diseases, would be clearly inappropriate on user talk pages. That doesn't mean such images should be deleted.
We should simply consider this vandalism, and improve the tools we use to deal with it. 1) helps a great deal already. Single login will also help, as people will not suddenly be thrown into a wiki whose language they do not speak once they have set their language user preference. We may, however, want to consider disabling InterWiki redirects specifically for non-Wikimedia wikis whose policies are beyond our control.
All best,
Erik