Yes that is a problem and it does involve trust. Conceptually It can be alleviated with having the coins in multisig address where a third party creates one of

Yes that is a problem and it does involve trust. Conceptually It can be alleviated with having the coins in multisig address where a third party creates one of the signing keys and the original thief retained one, and ideally the second recipient also had a third signing key. Still have the problem of getting the third signing key generated in a way that required no trust, in advance