It doesn't have to, but unless it is located in Iran, NK or other US-unfriendly place, US govt can always pressure the local govt to pressure the local business to turn things over. I wouldn't, for example, count on countries like Switzerland, US is already getting to its banks to turn over US accounts, and is supposed to be one of the most independent and un-influenced countries.
With the current legislation trend, eventually un-cooperative or "terrorist friendly" sites would just be filtered out and blocked, so you might have a hard time accessing your email. Some messages might never make it to you.
You're assuming the service has to be located within the US. Why?