The token is tied to a session cookie; when the session goes away and the cookie disappears the token will be rendered invalid. The reason replays work in Fiddler is that Fiddler is capturing (and replaying) both the session cookie and the form token.
You could simulate session expiration by removing the request's Cookie header from within Fiddler before replaying. The server should then reject the form's __RequestVerificationToken field.