Похоже, самый надежный способ проверить соединение с Интернетом, это сделать запрос к какому-нибудь редко падающему сайту, например google.com или microsoft.com. Хотя в ГОРФ хрен знает, что завтра заблокируют :).
Как я понимаю, седьмая и десятая винда примерно так и поступают, периодически обращаясь к каким-то майкрософтовским серверам.
В сети рекомендуют способ с NetworkInterface.GetIsNetworkAvailable() или экспортировать функцию InternetGetConnectedState из wininet.dll, однако у меня оба способа нагло врали, показывая наличие интернета при его отсутствии, но при наличии подключения к локальной сети или VPN. Сделать Ping тоже не всегда возможно, ICMP могут быть вырублены на стороне провайдера (или сервера). Так что пока способа лучше, чем сообразить запрос с помощью HttpWebRequest не нашел.

При этом способе, правда, есть два небольших подводных камня. Первый ВНЕЗАПНЫЙ, оказывается, ответ на запрос все-таки надо прочесть, хотя сам ответ в данном случае и не особо интересен, для проверки достаточно отловить код ошибки в try/catch примерно так:

request = (HttpWebRequest)HttpWebRequest.Create(URL);

//[...]

try
{
    resp = (HttpWebResponse)request.GetResponse();
    //не вывалились в ошибку, значит все OK

    Stream temp = resp.GetResponseStream(); //если не прочитать поток ответа
    //случается потеря соединения при повторном запросе (сам в шоке)
    StreamReader sr = new StreamReader(temp);
    sr.ReadToEnd();
	
	//Обрабатываем случай когда все ОК
}
catch (WebException ex)
{
	//Обрабатываем ошибку соединения
}

Ну и второй подводный камень довольно очевидный — операция запроса к сетевому ресурсу довольно долгая, так что желательно делать все это в отдельном потоке, дабы не грузить основной поток, в котором обычно интерфейс своими делами занимается, а то программа будет выглядеть «зависшей».

Пример на GitHub