<p>Is anyone aware of a (preferablly free) webservice that would accept a SOAP or REST request.</p>

<p>This request would contain an IP address, and the service would return an approximation of that IP's location.</p>

<p>EDIT: I need resolution down to the city of possible.</p>

MaxMind
do a fairly cheap one. You send the IP as a query string parameter, then it sends you back either a 2 letter code or an error code. We used it for quite a while before moving to our own lookup tables, and it's quick and reliable.
Found the link:
http://www.maxmind.com/app/web_services#country
- it's $20 for 200,000 lookups which isn't bad value at all.
EDIT: MaxMind also do a service with resolution down to the city:
http://www.maxmind.com/app/web_services#city
. It's a bit more expensive at $20 for 50,000 queries but that still isn't too bad. I can't vouch for the accuracy of this service though as I have only used the country resolution one, as that's all we need.