Won't help fix the problem, but may narrow things down
While this won't help any of you (sorry), I have an HTC HD7 on T-Mobile and have no issues with international travel with it. I do typically swap out for a local SIM wherever I travel (T-Mobile will let you unlock your phone for free), but I have also left my US SIM in the phone on occasion while overseas. Switching between Global and CDMA-only has worked perfectly.
I understand that this doesn't fix anything for any of you, but it might at least indicate that this is a Verizon issue rather than an HTC or WP issue, although I suppose that since the trophy is a different model than the HD7, there's still the possibility that it's the device that is the issue.