I can recall that once I resolved similer issue by setting the Execute ACL to anonymous and then restart the server.
Another possibility could be, that if you set the ACL of your service to anonymous, and pass a wrong user credentials, you will receive Access Denied exception.
To understand the authentication of a web service in webMethods following content might be helpful.
The Integration Server’s SOAP RPC and default processors do not authenticate a client’s user ID and password (credentials) when they receive a SOAP request. Instead, they authenticate a client just before invoking the target service. If the client’s credentials are not valid (as specified by the Execute ACL associated with the target service), the processor returns an HTTP 500 status code. A 500 status code indicates that the request could not be fulfilled because an internal error occurred on the server.
Certain SOAP clients (.NET clients, for example) issue an authentication challenge before submitting their credentials to a server. These clients do not supply a user ID and password when they transmit their initial SOAP requests. Instead, they provide these credentials only when they receive an HTTP 401 status code (which indicates an authorization error) from the server. Because the Integration Server’s built-in SOAP processors permit anonymous access, these clients never receive the 401 status code that will cause them to submit their credentials.
I am not sure how XML Spy passes access parameters, however you might get some idea if you compare the SOAP envelope generated by XML Spy and webMethods connector.
Let me know if it helps.