If you were a resident of the country where the name change was done, I would expect that name change would be recognized in the US. It's just a matter of having an appropriate document from that country, possibly with a notarized translation, to show to agencies in the US to get them to change their record of your name.
If you didn't take pains to get official documentation of the name change in a form that will be accepted in the US, going through a redundant US name change might be cheaper and faster than trying to get the right documentation from the foreign country from afar, especially if you don't have a good command of the language used in the other country.
The key form for new employment is Form I-9. The instructions with that form do not make any mention of the employer doing connect-the-dots to link the name you want to use to the name on your ID. The certification the employer's representative must sign says "Certification: I attest, under penalty of perjury, that (1) I have examined the document(s) presented by the above-named employee,(2) the above-listed document(s) appear to be genuine and to relate to the employee named, and (3) to the best of my knowledge the employee is authorized to work in the United States."
If the name on the passport has the same middle INITIAL as your new name, you're all set, because you only have to put the initial on I-9. If the new middle initial is different, it's up to the employer to decide if the foreign name change document is enough to make the passport in the old name "relate" to your new name.
