Just wanted to come back and share what seemed to fix this issue for us, just in case it helps anyone else.
In our case, we were automatically redirecting users to WHMCS using a dynamically-generated AutoAuth link. Since the redirect was happening at the same time the link was being generated, there was absolutely no way the link should be coming back as expired, but it was.
Also, in our case, the link to WHMCS was happening on another server from where WHMCS runs, where we run our main project site. We had checked time/date settings on both servers to make sure they matched (and they did). However, we believe there was a slight (1 second?) difference causing the timestamp on the originating server to be slightly *ahead* of the server WHMCS runs on, and that this resulted in the "link expired" issue. It wasn't that the 15-minute timeframe had passed; rather, WHMCS detected that the timestamp represented a time in the future.
We fixed it by subtracting 30 seconds from the timestamp before hashing it and creating the link, and, since doing that, we haven't see the issue again.