For the general question, the accepted practice is pretty much to tack on the word that modifies the larger phrase at the end, with a hyphen, as with -san. Unless of course the "word" carries its own punctuation, as the possessive 's.
For your specific problem, I can think of two options, one of which you've already mentioned.
The first option is to simply use English honorifics (Mr., Ms., Mrs.) when communicating in English, and Japanese honorifics when communicating in Japanese. This does carry the disadvantage that English honorifics are not genderless (and also not really honorifics, exactly), but there are usually other ways to phrase your greeting in the case of unknown gender.
The second is to add -san after the final name (it doesn't matter if it is the surname or not). Perhaps italicize it as Erik Kowal suggests. -san is used in English, but I've no idea what effect reading it would have on your co-workers, if that is not company practice. Which brings me to my final point.
The more I think about it, the more I question whether this is really a matter of English usage, and not rather something you should be asking your employers. It is their company policy, after all, if I understood your opening paragraph correctly. Your best bet is to either ask them directly, or observe how they write their own letters and company documents.