Or after initial token use, set to expire after n seconds rather than immediately

That's exactly the approach I'm leaning towards using.

Or you could trigger an ajax call on the page that actually checks the token validity then redirect the user to a new password or a sorryexpired form.

Gmail may fetch the page but wont run the js on it.

Edit: this works for situations when spam filters fetch the links as soon as the mail arrives.

Yes, please ruin functionality without javascript for the sake of gmail's nosiness.

Comment about a form and PUT/POST is good - it will work by standards in any browser, even when gmail starts executing javascript. Add auto-submit on top javascript if preferred.