Additional Configuration to disable anonymous session cookies?
Make sure the $cookie_domain is set properly in settings.php, often if it's not set to the correct domain, particularly in proxy situations, you'll see inconsistent login behaviour.