Solving error: The remote server returned an error: NotFound

I had a weird issue today. I am calling an external website using WebClient inside my WCF application, and I consistently got this error in WebClient call: "The remote server returned an error: NotFound". The error did not give me enough clues. To debug it, I ran fiddler and to my surprise, the error doesn't happen when running fiddler. The error occurs only when not running fiddler.

Did a web search and suprised that no one seem to have hit it before. So writing this post. I asked my colleague Gopal Srinivasa and he immediately pointed out that we are behind proxy and we need to install Firewall Client/web proxy and it immediately solved the issue!