I've worked in a place in Europe that had some people telecommute from Mexico. So I know it's both possible and legal^†. Never had much to do with them so how well it worked, I'm not sure of. But AFAIK, they're still telecommuting from Mexico. I've also done consulting gigs for banks were people on other continents were effectively telecommuting. (That didn't always work very well, but it probably wouldn't have worked very well either if they were sitting down the hallway).

^†What often happens with foreign telecommuters is that the business creates a small daughter company in the country the telecommuters work in, and hires the telecommuters via the local daughter company.