When I visit the ICO site I also get a "civicCookieControl" cookie which you don't list. I guess that this is probably coming from javascript and your site isn't processing this?
Also interested, I've tried similar things with watir webdriver and a xvfb/headless mode but the only real 'solutions' I've come across are time-outs. Needless to say it could've been heaps better.
I didn't do much testing since PhantomJS 2.0 but I know that in the past, it was recommended to reload PhantomJS every +/- 50 pages to free the leaked memory.
It could also be that the cookies handed out vary geographically, or if a page includes adverts in iframes via an ad provider network the cookies you get will depend which member of the network your request is redirected to this time.