If this is .Net - and you haven't specified what the platform is - then you could try adding this configuration XML block in the web.config of the web application not the service). It needs to go directly inside the root section:
Equally - you might find that the config already has an entry for system.net in there somewhere which is directing the requests out to a specific proxy, in which case replace it with this.
EDIT - In response to your comment
Out of interest - does the service layer attempt to make a call to the outside world? I'm just wondering if you're actually getting an error on the service method that is getting bubbled through the service back to the website code - if this is a SOAP/wsHttp service then .Net could well be persisting a proxy auth error from the service layer back to the calling code.
As a final note - I would use Fiddler to debug the web traffic on the machine - that way you can see exactly where requests are going, which processes are requesting them, and why they are failing. What this won't capture is all the traffic that is hitting 127.0.0.1, as the HTTP subsystem usually bypasses any system proxy for loopback. However - something is trying to access an address that requires a proxy, and with Fiddler running you should see what it is - and what the address is.
A Final, final note
Okay - so the request is going out to ISA - it's not IIS doing this, it's code, or at least configuration values that the code uses, that's doing this. If you can't track down these values and disable the firewall usage then one thing you can do is to switch the application pool's identity over to using Network Service - so long as the machine is allowed out of ISA, it will successfully authenticate through the proxy, thus solving all the problems.
It would be helpful to know, however, how this webservice call is being made (.Net, Java etc) because there are numerous different ways they can be affected depending on this.