It is not unusual to have so many 407's. That's how it works. If your browser opens 10 TCP session to a web site or proxy, each of those 10 session gets authenticated when you open the page.
However, you also want to make sure they are using the setting for 'Use HTTP/1.1 through proxy' in the IE settings. That will reduce the amount of 407s. IE6 had this option turned off by default. IE7/8 has it on by default, but it still could have been turned off for some reason. Just make sure it's checked.
Look in the actual access.log for the request "GET http://www.google.com HTTP/1.X" to see if the client has 1.0 or 1.1 turned on.
Is there anyway to just authenticated every 15 mins or so? 'Use HTTP/1.1 through proxy' is on in our browsers.
I know with our transparent authentication rule I have it set to 8 hours. I tested it and it works great. I authenticated once in the morning and then once as I was just about to leave for the day.