In short, have the option to set up 3 (or however many stores) with *different* products,
So it has to be set manually. If the user wants to display five unique products for example, he/she must choose total 15 items manually in order to associate three different locales in that case. I would hardly imagine average users would love to do it.
You mentioned that have a default set but it's not possible to find a product that is not available in the other stores. In that case, linking to the search result page would be one solution and it is what is said in the initial reply.
If call was made via JS it would even be compatible with caching plugins...
With the URL cloak feature, it's possible to avoid using JS scripts.
Overall, I would just use the mentioned plugin in your initial post until the feature gets implemented. Thanks for the suggestion though.