Sounds like forwarding to a 'go' search on the foreign wiki, rather than directly to the given page name, would do what you're asking for. If an exact match is found on the foreign target wiki, you'll get forwarded a second time to the target page; otherwise you'll get a search results page on the foreign target wiki.

This of course requires that we know which interwiki targets are MediaWiki sites and which aren't.

So the point here is that for "foreign" titles the search only checks whether they're valid titles and redirects if they are, while for local titles we also check for existence? I don't remember if @TTO's updates around importing made such checks easier.

No, it doesn't really have anything to do with what I did.

I wonder how useful this really is. After all, typing interwiki prefixes into the search box is a very advanced feature, and so we have to wonder whether those advanced users prefer the existing behaviour.

In T22603#2468209, @TTO wrote:

I wonder how useful this really is. After all, typing interwiki prefixes into the search box is a very advanced feature, and so we have to wonder whether those advanced users prefer the existing behaviour.

Indeed. Personally, I often use the interwikis to get to a red link; one can also click the search link from the noarticletext. I tend to decline.