So i was having a problem with certain sites using localStorage, like this one. The error messages varied(and the linked one just plain didn't work), but the Javascript console produced a "SecurityError" with the message being only "The operation is insecure.", as if localStorage was disabled, which it definitely was not.

Digging into the source code, i found the function DOMStorage::CanUseStorage(in mozilla/dom/src/storage/DOMStorage.cpp). The logic there uses various logic, like checking for the dom.storage.enabled config variable and checking if the permission manager denies the access. This last part effectively checks the cookie policy setting (not so surprisingly, thinking about it). When nothing site specific is set up, the default settings get checked, and if the default setting is deny cookies, allow cookies or only allow session cookies, all is fine. The only setting that leads to really surprising behaviour is when you have setup seamonkey to ask about cookies. In the case of accessing localStorage, that case leads to the unconditional denying of access, instead of asking for permission.

I know this now, but that seems to be a quite underdocumented sideeffect of that particular setting.