The ability to work in the US is NOT dependent on completing a US residency.
Both individuals you speak of came to the US to do additional PRS training after completing their primary qualifications abroad.
While it is true that many programs prefer an ACS BE/BC surgeon (which requires completion of a US/Canadian general surgery residency), they are not required to take one who is or who has done their residency in the US. You will note that neither of these surgeons is Board Certified by any American institutions. Baylor has a long history of taking foreign trained surgeons into their PRS program, especially when Shenaq was there.
For most people, not being BE/BC is a problem because of the issue with getting on insurance plans, hospital credentials and patient preference. However, in an academic institution, it is not as much of a problem especially if you have a large cash paying population (who don't use insurance).
As long as you are eligible for a state medical license, and have completed training acceptable to your employer, there is not a problem training outside of the US if you are not required to be BE/BC. It is quite common actually to come to the states for fellowship, after having trained elsewhere, and stay on...I see it quite a bit in anesthesiology, for example.