Your point about using URLs encoding language information is what we did at Greenpeace Planet (see
http://greenpeace.org and
http://greenpeace.nl, or if you prefer
http://greenpeace.org/international_en and
http://greenpeace.org/nederland_nl).
We used cookies only to make the user's language choice persistent when revisiting the generic http://greenpeace.org site. If you turn off cookies, navigation works fine. We set some global connection values that make it simple to make internal links that link to the right language version.
Check out the "case study" one-page note I wrote for the presentation Carl references in his first note.
Now ... our work wasn't completely generalized so Lars will have some work to do when trying to figure out just how to generalize some stuff . But he did work with me on the Greenpeace project so he's familiar with how that works.
Be sure to read and comment on the specs as they evolve.