An internal ID for a customer record is probably tied to the orders and other internal data. Deleting a record just breaks shit you might need for historical purposes.
It's better to disassociate the customer info and maintain the other links - unless there is an obligation to do so otherwise (unfamiliar with gdrp nuances)
Randomizing multiple foreign keys at the same time is interesting though. Is it really necessary if the company isn't intentionally being malicious trying to maintain and advertise to the requesting individual ?