You should always be logging in to https://test.salesforce.com/ for sandboxes, and https://login.salesforce.com/ for production instances. Your firewall should likewise be configured to allow connections to https://*.salesforce.com/. This is to allow load balancing, future expansions, etc. Edit: The login response includes a serverUrl that should be used for all future requests. Your client should be resetting the endpoint after logging in.
Edit 2, Code Sample
I wrote up an example login script using Visual Studio 2008. It took me some time to find a syntax that worked, because C# created bindings that were not like the examples on the developer site Quick Start.
Here's my basic example (no error checking):
// Create a client
SforceService.SoapClient client = new ForceTools.SforceService.SoapClient();
// Attempt to login. You should catch faults/exceptions.
// The two nulls are headers I'm not using.
SforceService.LoginResult lr = client.login(null, null, username, password);
// Create a session header for future calls.
SforceService.SessionHeader sh = new ForceTools.SforceService.SessionHeader();
// Assign a session ID.
sh.sessionId = lr.sessionId;
// We need to reset the Endpoint. For some reason, C# wouldn't let me actually
// set a new client.Endpoint.Address value, so I just trashed the original
// client and created a new one with the reset URL.
client = new ForceTools.SforceService.SoapClient("Soap", lr.serverUrl);
// Now I can do things like query. Those nulls are various headers I could set.
SforceService.QueryResult qr = client.query(sh, null, null, null, null, "SELECT Id FROM Account");
This successfully returned records from my demo org. This binding was the partner.wsdl; I assume the Enterprise WSDL is easier to work with. If you find a better way get this to work (e.g. actually be able to set the Endpoint without re-initializing the entire client), I'd be glad to see it.
Best Answer
Enable Apex Debug logs the SOAP request and responses are output to these. The Debug log Category of Callout is describes here as follows...
The easiest way to capture an Apex Debug log is to have Developer Console open when you perform the operation in the UI, as described here. The more traditional route is to go to Debug Logs under the Setup menu. Both give the same results.