The i18n.txt (reading much smoother than my version!) should point out that the LocaleMiddleware? needs to be _after_ the CacheMiddleware? (if used), because it modifies the Vary-header. Otherwise the accept-language header wouldn't be used correctly.
And it is a case for #730: the LocaleMiddleware? needs in process_request access to the session, so must come _after_ SessionMiddleware?. But SessionMiddleware? and LocaleMiddleware? must come _after_ CacheMiddleware?, so that the caching sees the Vary header in process_response (due to the reversed order of middleare). That's exactly the kind of "order deadlock" the user can't solve without giving explicit middleware order.
I copied the above text to #730, too.