Winnipuh,

Готового решения не предложу, но вот мои мысли на эту тему: все зависит от того, до какой степени вам требуется проверка:
нужно проверить, только доступность сервера и указанного адреса. Самое простое, что мне представляется - просто установить соединение по указанному адресу попытаться что-то прочитать. Если вы используете http, я бы предложил всегда подключаться по базовому адресу сервиса и пытаться считать help-страницу.
Можно сделать это, например, с помощью System.Net.WebClient . Здесь достаточно просто получить 200 ответ (что удалось все считать)

нужно убедиться в том, что пользователи не только указали доступный адрес, но и указали именно нужный сервис. Здесь я бы поступил одним из способов: а) ввел специальный тестовый метод в сервис. б) прочитал метаданные и убедился (хотябы по имени сервиса), что это мой сервис.
Последнее легко делается связкой System.ServiceModel.Description.MetadataExchangeClient и System.ServiceModel.Description.WsdlImporter .

P.S. Прошу прощения за задержку - боюсь, все написанное для вас уже не актуально.