It varies by stage of VC.
For me, as a “late seed” investor,
(i) I look for a CEO who has already moved, or is in the process of moving here — although I don’t care how much of the rest of the team is here;
(ii) I require the company legally to have “flipped” to a U.S. company before the investment closes.
A “flip” for European start-ups used to be a bit of a headache, but now all the top Silicon Valley law firms can do this easily. Gunderson and Orrick in particular have worked closely with YCombinator, and now I believe almost all foreign YC companies are “flipped” before Demo Days.
Most U.S. VCs traditionally do require the CEO to be in the U.S., but especially the later stage you go, the less VCs care. By $10m in ARR or so, no one really cares where you are headquartered … because you’ve proven you can scale. No one cared Atlassian was HQ’d in Australia, when Accel invested $60m … but that’s in part because Atlassian was already pretty huge.
The reality is that on the one hand, more and more U.S. VCs are getting on jets to do deals. But in the end, a decent percent of them, especially in B2B, would prefer the CEO to be an Uber-ride away. Not all. But a decent percent.