Cookie only detected when visitor is logged in

ANSWER TO MY OWN QUESTION

This was something I had been trying to debug for the last couple of days. And the answer was found by mistake.

What caused the error was caching. I had to exempt the cookie from cache in order for it to work as it should.

So, if you are experiencing this behavior and start a debug quest that you know will bring you pain and misery, check your server settings or give your hosting provider a call first.