I think it is solvable. Your instance keeps track of the instances it is connected with. It could just do the search and find the post on your own instance if the domain is among the connected other instances.

EDIT: Right, it doesn’t fix the problem of stumbling upon a link to a fediverse instance somewhere else. Not sure how you could deal with that one