So we are talking about "external" keys (ie. visible outside the database). We are back to square one: externally visible surrogate keys are problematic because they are detached from real world information they are supposed to identify and hence don't really identify anything (see my example about GDPR).
It does not matter if they are random or not.
> How are you going to trace all those records if the requester has changed their name, phone number and email since they signed up if you don't have a surrogate key?
And how does surrogate key help? I don't know the surrogate key that identifies my records in your database. Even if you use them internally it is an implementation detail.
If you keep information about the time information was captured, you can at least ask me "what was your phone number last time we've interacted and when was it?"
> I think that spirals into way more complexity than you're thinking.
This complexity is there whether you want it or not and you're not going to eliminate it with surrogate keys. It has to be explicitly taken care of.
DBMSes provide means to tackle this essential complexity: bi-temporal extensions, views, materialized views etc.
Event sourcing is a somewhat convoluted way to attack this problem as well.
> Those queries are incredibly simple with surrogate keys: "SELECT * FROM phone_number_changes WHERE user_id = blah".
Sure, but those queries are useless if you just don't know user_id.