Has the natural rate of unemployment decreased with modern travel and the Internet? The natural rate of unemployment is a combination of structural unemployment and frictional unemployment.
Structural unemployment is caused by a surplus of labor at a given wage in a given area.
Frictional unemployment is caused by workers searching for or transitioning between jobs.
However, modern travel (airplanes, automobiles, etc.) would reduce structural unemployment and frictional unemployment by allowing for faster movement of excess labor to transfer to areas with a shortage of labor; similarly, the Internet (specifically search engines, online jobs fairs, etc.) would reduce frictional unemployment by allowing for workers to search for and find jobs more easily.  

Does this imply that the natural rate of employment decreased with modern travel and the Internet?
To me, it seems that it has increased, not decreased, due to the factors you mention. Yes, transportation and information networks enable workforce movement. But they also enable movement of goods and information - and because goods and information are more mobile than humans, they profit more, and the results of their portability outpaces the results of the workforce's increased mobility. 

When goods were hard to move, a local demand had to be met by local suppliers. If a manufacturer lost a deal, it went to a local competitor instead, and the workforce could adapt easily. Now, if a manufacturer loses a deal, it goes to a competitor 5000 km away. Take for example the Ruhr area: it's still the most densely populated area in Germany, even though the steel industry which attracted workforce in the mid-20th century is gone. The Germans literally shipped one of their steel mills around the globe to China - but the workers stayed. 

So, because the workforce cannot adapt to structural changes with the speed at which they are happening, the structural unemployment is higher than before networks which enabled such changes. But the increased speed of change also means more frictional unemployment. A large part of the adaptation which is happening requires people to change jobs. Also, your observation of an increased commute radius contributes to frictional unemployment too - when a person is unhappy with his job, he has more opportunities in his now increased commute area, and is more likely to change jobs. 

There are lots of indirect effects too. The Internet and the transport networks enable changes in culture (e.g. today people move out of their birth town early, so may be more willing to relocate again later), business models (e.g. movie streaming) and market structure (today's trend towards ever larger corporations is enabled through, among other things, efficient information and people movement, which reduces overhead costs of giant companies, and global knowledge - I doubt that 50 years ago, an American chain for mediocre coffee in fancy large cups would have been able to establish itself in Europe. Nowadays, the culture export means that the trendy European teenager recognized the brand before they had one of the shops in their location). And they go both ways - a giant corporation may actually be more stable, and afford to keep workforce during short-term demand slumps which would have capsized a tiny manufacturer. 

Whatever globalization (spearheaded by more exchange of information and goods, and even people on their respective networks) may bring in the future, it currently seems to create more unemployment - not because it's a bad thing in itself, but because in a more dynamic market, there is less job stability.