Your situation appears to be relatively unique. Have you tried turning all Safari extensions off? Didn't you used to run the Cookies application? Could there still be remanants hanging around?
The only extensions I'm running are Roadblock and Wipr, neither of which should have anything to do with cookies.
I'm still running Cookie, but I've asked its dev about the issue a couple of times and haven't received a response, nor have any of his updates addressed it. I've now disabled Cookie to see if it accomplishes anything. (ryck is also running Cookie, and he apparently hasn't had any problems.)
The curious thing about this is that not all of my cookies disappear...only the ones that affect login.
Ah ha! I just focused and realized that it's the "Remember Me" cookies that are disappearing. (MacUpdate doesn't present me with the option, although it does remember me.)
Any thoughts on that?
