as the address say, when you send digitally signed message through exchange 2007 edge server, the message cannot be verfied on the destination, that has been raised for a while, by escalation case by myself, and after further investigation on that subject working with the support team whom they made a lot of work ( and me as well) i managed to fix that, it was a bug !
a bug in which when you send email from outlook in HTML format, it will reach the destination in unverfied format, and a red arrow in the front of head of the message, and that's only happen when you send HTML messages with attachement in it, that's also mean when you send HTML messages in HTML format without attachement it WILL be verified, so the problem came in sending attachement
sawing saw, i disabled the attachement filter on the edge servers, and voila ! it woked fine..
i reported that to Microsoft and hopefully a fix will be available on rollup update 2 for exchange SP1
btw, you still can use remove-attachementfilterentry cmdlet but i didn't tested that actually
Good luck with your implementation
Install Rollup update 2 for exchange 2007 SP1 and that will fix the issue