I'm back with more info about the cookie thing :)
Apparently, this happens only in chrome and I was able to reproduce it like this: you open multiple tabs, navigate to a domain, open phpmyadmin, browse some table, switch tab to something different than plesk (say facebook.com). Repeat this...