I really don't understand why server-side storage of the trace isn't a viable approach here, with only a unique key flowing to the client and back. Does it have something to do with how backend load-balancing works?

Yes, this storage would be growing exponentially making the disk space and latency problems harder (add the disaster recovery/backups). I think the choice of using client side is not too bad if you ensure that its secured properly. Also the company can excuse itself from the liability of storing sensitive data on its servers, thats a big deal in itself to be compliant for enterprise audits

1. The down side is that it cannot be used across the clients even for the same user

2. Using the same encryption key was a bad choice here, a per user key would have solved this issue for sure.