I failed to say that your token context should have a "time based expiration", in that a new token is reissued periodically as defined by you and your needs. I would refer to the ASP.NET Forms Auth mechanism with its sliding expiration.
I get that you can expire it, and that helps, but it's not the same as use-once. Of course, just using a timeout is probably fine in many cases, especially if it's used with SSL. But replay attacks are still possible since there's a windows where it can be re-used.
Replay attacks are always gonna be possible unless you use a one time token or signature, thems the break's..., unless you wish to get into the something you have and something you know model.
How can you do a use once token making concurrent requests without a strong authentication mechanism client side such as issuing private keys to clients....and all the PKI admin overhead.
I think its safe to say, that a restful api should be stateless, and bottlenecks such as session state are not necessary.
AFAIK, neither signatures or "something you have, know" alone fixes replay attacks. Since this is a well known problem in cryptography, many solutions exists. All of which are probably overkill for this use.
