We have this problem all the time on occasion. It has gotten better. A lot we've found is related to the headers not being fully in-place when received (e.g. something is different which causes it to fail). We just tell everyone daily to just double check their spam. It's not often but it does save a heartache.

Trusted Senders are still subject to SPF/RDNS checks to prevent spammers using your list of trusted users to deliver spam to your inbox directly. As such, the majority of the time these issues are caused by a problem with DNS lookups, and I would start there. Check the Delivery/SMTP logs for signs that lookups are failing, and you can test for resolution by temporarily switching to another or public DNS server.