Secure forgot password page: Is a server-stateless implementation viable?

Your question is well written, and you clearly understand the issues well. There is nothing fundamentally wrong with the crypto token approach you describe. Some things to be aware of:

• Most sites these days are database intensive, so storing a password reset token is little additional overhead.
• You should throttle the number of password reset emails that can be generated (e.g. max of 2 per 30 mins, for each email address) - which requires writing to the database.
• You are reliant on k remaining secret; this could be copied by a malicious administrator (or brute forced, if weak) - while database tokens avoid this single point of failure.
• A common (albeit minor) weakness with password reset schemes is the leakage of the token to external sites in the referer header. Having the token be strictly single use can help with this - although you can fix this weakness with crypto tokens as well.

There is a similar choice with generating session cookies - using crypto or the database. In fact, the performance considerations are much more significant for session cookies, as this work is done for every request. Despite the overhead, most sites use database tokens, for the minor security advantages.