Same problem here. Plus I am using sendgrid which automagically makes the link about 4 times longer using the same "trick" which further amplifies the problem.
In fact I decided that I should go the other direction instead. Now every outgoing email is stored in the database before sending. This makes it trivial to track every email open, every click on every link and the links look beautiful, like "/e/<random_email_id>/open". Been happy ever since.
Edit: This obviously doesn't invalidate the general idea.
Another benefit of generating and saving an email to the database first, is at that point putting a "view this email on the web" type link into the top of the email becomes trivial. Formatting HTML emails is a significant pain, and mobile only exacerbates that...
The point of a transactional database is, you know... handling transactions... and in this case, resetting a password is a transaction... Sure, you have to kill long standing transactions manually, but that's a fair bit better than having to deal with a url that is longer than https://foo.com/account/password-reset/(uuid) for users that may well copy/paste ...
While I do like and appreciate the idea.. it's easy enough to scale when you are either using a replica-set for your reads, or a sharded database...
A UUID is 128 bits, written in hex, so it's 36 bytes. If you use an appropriately URL-safe base64, you can encode a 216-bit value in the same number of bytes. That's long enough to be cryptographically safe for this application.
This of course is an email layer on top of your core logic. Your core logic still thinks it's sending a mail with a very long URL. It's just shortened and when it's incoming it will be converted back. So you get the best of both worlds.
Edit: This obviously doesn't invalidate the general idea.