From a tax perspective, locating the US office in a tax free jurisdiction is most wise. These states would include Washington, Nevada, Wyoming, Texas, Florida, and (sort of) New Hampshire. Also, setting up a relationship between the foreign entity and the US entity to minimize US taxes (as Microsoft has done --see above) certainly helps. Finally some attention has to be paid to the tax effects on the US citizens (or green card holders) and the non citizens (or green card holders). Most foreign tax questions involve an expert in the US as well as in the foreign jurisdiction.
As for legal issues - contracts are handled internationally all the time with ease. But liability issues vary dramatically from state to state and even more from country to country.
For a start up, unless the nature of the business is very liability intense, I would focus on the tax issues. As this article has shown, tax can be really, really expensive.