Geographic Data Web Service

Question

I am thinking about writing a program to check some mileage claims (about 45,000 of them actually) made by Members of the British Parliament recently.

The data I have is quite course - the origin and destination of the trips is generally provided only at the Town level. What I am looking to do is basically look at the mileage figures they have submitted, look at the "calculated" mileage obtained from a web service, and then compare / contrast. (I'm thinking of perhaps being interested in cases where the claimed mileage exceeds 40 miles, and the claimed mileage exceeds the website figure by a factor of at least 1.4 for instance).

Code wise I'm fine, but what I don't have is a webservice I can use to get the distances. Google Directions is out of the question (has to be used with Google Maps) - and I am looking at writing this as a console app in C#.

Can anyone suggest any suitable service?