Interface language is cached for anonymous visitors

Steps to reproduce from Roger Lopez - http://drupal.org/node/330156#comment-1119274

- I did the following test on a clean Drupal 6 install, with only locale and translation turned on. I have 2 languages set up, English (default) and Spanish. Page caching is set to "normal", and language negotiation set to "path with language fallback".

I used 2 browsers to cleanly represent 2 separate users. I set Firefox to use Spanish as the first language, to simulate a native spanish speaking user. I used Safari with no changes to represent an english speaking user.

The domain I was testing on is simply drupal6 so the site root is http://drupal6/.

1) While logged in as admin, clear the cache.
2) Log out. Since I was in Firefox, I ended up at http://drupal6/es
3) Go to the site root (without the language prefix). The page is still in spanish.
4) Now, in Safari pull up the site root. The page is in spanish.

So whichever language a user hits the front page with when the cache gets set, all subsequent anonymous users get served the page with the interface translated into that language.

A couple of ideas, neither that pretty:
1. Only cache pages in the default language for the site (not ideal, but possibly an option for Drupal 6)
2. Cache pages with the language code added to the cache key - this would be great, except that information isn't yet available when the page cache gets set afaik

I'm not sure how the language negotiation gets set, and whether this can easily be done with simpletest quite yet, but it should be possible to write a test for.