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.