Please see this article, in particular the section on Transparent Modes.
Basically you fell into the "admin trap" of believing that you can avoid modifying the clients and still get authentication to work without prompts. When you use a transparent method, the client machines do not know they are going through a proxy, so you cannot use proxy authentication. For "promptless authentication" to work, you need to use NTLM or Kerberos, but the browser will only send credentials for trusted sites. When the web gateway prompts the browser for authentication, the client thinks the remote site (cnn.com, facebook.com, mcafee.com, etc.) is asking for their domain credentials. Obviously you wouldn't want that to work.