I too noticed this problem. It seemed to mysteriously appear after updating to 10.6.8. Also tried all of the solutions you did (short of reinstalling everything) to no avail. The only way I was able to completely block cookies was to select "never"under preferences and turn private browsing on from "file" in the Safari menu bar. Of course, when you first open Safari, you will get cookies from your home page as you cannot set private browsing as a default. Once Safari is opened, set private browsing, empty all cookies, and it should work. It is a pain and a hassle but at least it will block what you don't want showing up on your computer until Apple issues a fix. Good luck.
This is true. The "block cookies always" setting in the Privacy tab is not 100% effective (evidently Apple programmers have their own definition of "always").
There will not be a solution from Apple. They don't care. Users that want to block cookies are almost surely poor consumers and probably troublemakers too.
dfp mbp's fix will work but what a pain.
It used to be one was willing to pay the Apple "tax" for a superior product, but that was then ...
Make your next computer a PC that runs Linux.