Well I was able to solve the problem. It seems that the application has a setting called ConnectivityStatus.IsOffline that is application / user specific that I have to hardcode to "False" so that it always tries my service. It seems that once my application couldn't reach the service then it went into an "offline" mode. Once in the "offline" mode not even a reboot would pull it back out of the "offline" mode.
http://msdn.microsoft.com/en-us/library/bb546195(v=vs.110).aspx http://msdn.microsoft.com/en-us/library/system.web.clientservices.connectivitystatus.isoffline(v=vs.110).aspx