Answering my own post here, it seems that WP Super Cache has a dedicated setting (in Advanced section) to not cache urls that have a GET parameter. Once that is checked, problem seems not to replicate for me anymore.
So indeed the root problem is that cached files do not run the php code anymore, hence setting cookie from php fails and probably JS is a better option.
There might be other ways around it to force cookie setting specifically, look for example at wpsc_add_cookie functionality.