Core

Ok, the problem is the unset() of the FE user in
typo3/sysext/frontend/Classes/Controller/TypoScriptFrontendController.php:1288

So if the session data is stored afterwards, no user is present and the cookie is removed.
This is indeed tricky.

However, I would like to know your usecase:
Why do you disable login on those pages?

The user and usergroups are indeed reverted/unset in the TypoScriptFrontendController.

Our "public" area is a mix of public (detail) pages and some list/basket type of views that contain USER_INT scripts that could write to the session.
They don't require separate entries in the cache for a different usergroup and should never contain content based on a fe_user.
We'd like to use 'config.sendCacheHeaders' to instruct a reverse proxy to cache the public pages.

In this scenario it somehow feels wrong that the same cookie (fe_typo_user) is used for both session and login handling :-)

The problem could also occur when using a FlashMessageQueue which is flushed after displaying messages and therefore causing an empty session to remove the cookie.

While I understand the intent, I've to tell you that this won't work out: If you've USER_INT on a page, "sendCacheHeaders" will not work.
Moreover it does not make sense to have some basket-like thing on a page with cache headers, since the user will potentially not see an update.
Same goes for the reverse proxy.

Regarding the unset-problem, I guess there's no correct solution except having separate cookies for session data and login.

It works out perfectly for our scenario, only the list view (1 page) does not have to be cached (USER_INT). We don't want separate page cache entries for every usergroup combination in the TYPO3 page cache for this (public) section of the website.
All the other static pages (information pages and detail views, around 10000) can be cached and send out the correct caching headers.

Fixed it now by making sure that no NULL values are written to the session triggering cleanup of the cookie.

Separating the login and session cookie would be a nice solution, but not easy to implement in core.
Another solution would be to keep track of the situation where the fe_user->user is initialized and later unset by a 'checkIfLoginAllowedInBranch' and take this into account when deciding to remove the cookie.

There are some other reported issues of users (randomly) being logged out, they could be related to the fix in issue #55549

So your usecase is that only one of a large amount of pages will not be cached, but all others will. I understood that wrong then before.

We can look at the problem differently. Lets say that having a valid FE login is actually just "data of the session". Hence the session is actually not empty. ;-)
Therefore we don't need a separate cookie for the login, but a single one for session data suffices.
The fix is therefore, as you described, to remember the actual login somewhere to be able to properly detect that "additional session data" before removing the cookie.

Patch set 2 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at http://review.typo3.org/37160

Patch set 3 for branch master of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at http://review.typo3.org/37160

Patch set 1 for branch TYPO3_6-2 of project Packages/TYPO3.CMS has been pushed to the review server.
It is available at http://review.typo3.org/37869