The issue is caused by the Enterprise Page Cache.
The form key is created at:
app/code/core/Enterprise/PageCache/Model/Processor.php:422
which ultimately calls setcookie()
.
Then the cookie value is retrieved at:
app/code/core/Enterprise/PageCache/Model/Observer.php:1043
in the same request.
As the headers/cookies have not been sent the value returned is null. This causes the core/session cookie to not update with the value Page Cache has just created which is supposed to happen at:
app/code/core/Enterprise/PageCache/Model/Observer.php:1045.
The patch below will resolve this issue.
https://gist.github.com/cmtickle/477aba06d8d6a69148de542bfb56ed45