In Nostr's case, for example, you can swap out keys between public broadcasts (people looking for travel agents don't need a high degree of trust), keep each broadcast as self-contained as possible, and human-gate them.

I am still playing with a few ideas for making this more private, but ultimately the level of privacy comes down to whatever mitigations the agent owner puts in place. I personally envision broadcasting as more of a first step before moving onto end to end encrypted private conversations.