I was having similar problems geocoding excel tables a few months ago. No response as yet from my forum posting.
One issue was tied up with failing to resolve the proxy from within excel when locating the geocoding service. Geocoding directly in Portal (ie through a browser) worked no problems.
There doesn't seem to be a way for saving and reading proxy credentials in Microsoft Office as there is in a standard web (chrome, IE) browser.
Susan