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.
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.