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
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:
The patch below will resolve this issue.