When you delete cookies in Safari 4, whether from within its Preferences dialog or in some other way, they will all mysteriously reappear anywhere from a few minutes to perhaps an hour later. I've seen several accounts of why this happens and how to prevent it, but none of them worked for me.
What did work is this: after deleting the cookies, quit Safari immediately, before it has time to restore them. When you relaunch Safari, the cookies will be gone for good. Apparently they're being cached in memory and written back to the Cookies.plist file periodically.

