Fundamentally, that's not a thing in the long term. Trust lasts until the next bad quarter if you're lucky, because ultimately a company will choose to abuse your trust rather than go under.
I don't want to come down too hard on companies here, they exist to make money, that's what they're for (and plenty of them provide very useful services).
But the concept of trust doesn't make a lot of sense here. The people that make up a company aren't constant, and if you do find a company with trustworthy employees, they won't take your data with them when they leave, they will leave it for the next person to abuse.
Trusting a company beyond what they explicitly promise (anything in a EULA-like document that says they can change things at any time doesn't count) is setting yourself up to be screwed down the road.
The os would just pretend those contacts don't exist when all contacts are requested. There could be a checkbox to share protected contacts on the permissions prompt in case you're trying to actually export them.
GDPR is a good example of a law that the US sheepishly somehow chooses to obey EU law (wtf, why didn't the US obey the EU laws around recycling and energy and no free plastic grocery bags for the past decade? and all of a sudden they care about obeying GDPR?), but do Central/South American, African, Middle Eastern, and Asian countries take a crap about GDPR? Generally not. They don't care about EU law. It doesn't apply in their jurisdiction, and they are not sheep. That isn't to say privacy doesn't matter, it's just that the law needs to be locally implemented, not obeying some arbitrary EU interpretation of the idea that wasn't even discussed with them.
As such, I think technical approaches are generally superior to regulatory approaches in user protection. They apply across the entire world instantly.