The first issue is indeed that the wrong interwiki has to be removed on _all_ languages to stop it from returning, but even with that one could still get into problems because there might be bots that visited some languages _before_ your removal, and others _after_ it. They would then consider the wrong interwiki to be a missing one on the languages visited afterward, and re-add them there.
Working with {{nobots}} as you have done is not a good solution, I think. Adding it on the Polish page could be justified, but on the English one it also stops a good amount of correct edits.
This particular issue I have now resolved by finding that there is a Dutch page on the same subject as the Polish one, and adding an interwiki to that one. This way, even if someone mistakenly adds the incorrect link again, for the bots this will lead to an interwiki conflict, so they will not automatically propagate the wrong link any more.