That was my issue, and yes, it absolutely is one of the many reasons why staging instances should have a caching on/off switch that mirrors production. It is absolutely 100% feasible that WPEngine's caching will break your site, and you need to know this before you push to production.
Don't get me wrong, as a contractor to a company that uses WPEngine, we have had a great experience with it - but e.g. in the case of setcookie() being completely useless for unauthenticated users, some documentation / warnings / big red flags would be nice.
In my case I was trying to build a simple site selector for unauthed users that would forward them to their selected site every time they hit the main domain. Nothing exotic by a long shot.
It sounds like you and ohashi don't understand how caching works. WP caching serves up static copies of your pages, bypassing the code and DB calls that would normally be required. Since your code is bypassed cookies won't be set.
This isn't something specific to WPEngine, this is how all the good WP caching plugins work.