I proposed enhanced interlanguage link manipulation/storage several times before (check the archive;-), and gave that some thought.
I propose a new, independent *database*, instead of just a table. We'll have to access another database from all but one wikis, anyway (we can't store a complete consistent copy of that table in all databases, now can we?).
That database could also hold other information, mainly a central user database, so multi-language users won't have to create new user accounts in every language.
Later, it could also be a place for the translations that are currently in the LanguageXX.php files.
Magnus