Further update: I am certain I know what the problem is (was) now, and the change I've just made definitely appears to have fixed it. I ran three tests back-to-back and all three worked fine.
For the developers out there, beware of how you encode hashes in PHP (I'd hazard a guess that's any variety of hash. I'm using SSHA (SHA1+salt), but I suspect the same holds true for plain SHA1 and MD5). If the hash contains any of the usual URL suspects (definitely "/" and "\", and probably "+" as well), if it's not encoded correctly it'll break in transit. That, basically, is what was happening some of the time with the old code. The new code takes a "standard" SSHA hash and rawurlencode()s it before adding it to the email. As I say, that seems to work unlike all my previous attempts.
And if you've never heard of SSHA before, look for the comment from "alex at milivojevic dot org 28-Apr-2005 06:45" in the function definition for SHA1 on your local PHP website mirror.