This has just started in ver 234.12. I noticed the same instances, In past versions the cookies were always gone upon cleaning....no re-boot necessary so I assumed that there is a bug in new version. I therefore reverted back to 233.1184 and the cookies are gone. I guess we'll have to await another re-version like 234.1201 to correct this. The reboot didnot do it in 234.12. That's whay I reverted.
Win XP Pro-SP3
was 234.1200
Now 233.1184
All cookies, IE and FF