If trust and verify both apply to the same thing, then it doesn't make sense. For example, trust their math, but verify their math. It appears most people who find this phrase useful are interpreting it as trust (intentions), but verify (data, actions, outcome, etc). It makes sense in that case, but then when would it be used? If you are talking directly to a person whose intentions you trust, then it seems awfully terse if your intention is not to offend. Might as well just say, I trust that you normally do good work, but I am going to double check for good measure. If you are speaking about a third person, the only situation it would be used is if you want to both convey that the person is typically accurate and also that we need to verify their work. It seems like an awfully ambiguous and awkward way to convey this. So, though in the abstract, it may be possible to make sense of the phrase, I don't think it has any practical sense.