"Trust, but verify" comes from the Soviet Union and is an example of Russian humor. It helps that the Russian words for "trust" and "verify" rhyme.

It really means something like "act like you trust the person, but secretly, don't trust them and double check that they've fulfilled their commitments". Putting on a smiling face and acting as if everybody was acting in good faith, while secretly expecting the stab in the back because you would do the same, was key to diplomacy in the USSR, even between departments of the same government.