I agree fully with Olve Utne's solution. I don't think it matters that no:-links redirect to nb:-links. They are for the most part pointing to articles that would stay on nb: anyway, and after a while most no:-interwiki links will be changed to reflect the move to nb:. When it comes to static links on say Google or other search engines these will sooner or later be replaced by appropriate ones from nn: and nb: and the no: links will slowly die away. So in other words, it will be a temporary "problem", and both wikis will soon enough have required fully equal status.
Cheers, Bjarte Sorensen