All the other answers in here are also valid, but if none of them solve the issue it is also worth checking that the actual headers are being passed to the server.
For example, in a load balanced environment behind nginx, the default configuration is to strip out the __RequestVerificationToken header before passing the request on to the server, see: simple nginx reverse proxy seems to strip some headers