This was an odd one, so I want to get it down on paper before I forget what happened. 

We were deploying S4S into a load balanced environment. Everything worked fine in UAT.

Rolled it out to Prod and the site blew up with 

“__RequestVerificationToken” is not present

appearing in the Sitecore log file around the use of WFFM and S4S, but not showing as an S4S error. This seemed like a generic .net error but had not seen this in UAT.

What could be different? I'll save you the unsuccessful troubleshooting steps, as eventually we arrived at this one: We were pulling one server out of the production pool in the load balancer. In this customer's case F5 I believe. The load balancer was doing SSL offloading. Michaelangelo has been enlisted to draw this up below (dotted line indicates server out of pool):

So when you address the server outside the pool, you go to it in HTTP. In this case the 

<httpCookies requireSSL="true" />

causes the site to fall over on our web form, and that's what the _RequestVerificationToken is about. Solutions are to find a way to put the server back in the device and address outside the pool, or change the requireSSL tag for testing.