Have you seriously tried disabling your plugins and seeing if the cookie issue exists.
I would think this is going to come down to a plugin conflict or maybe some custom code in your header etc.
Our example here and the site I posted in threads clearly show as long as cookies are set right.
Now your cookies work absolutely fine without the vb3 headers so its something in your
vb messing up the cookie thing because our code of cookie authentication is working fine without the header. The very fact our examples work with the header might point to plugin or other code that might not be standard. This is where I would start.