Change of plan...

Well, our really good idea was to use agents to roam the network and build a massive grid of Point to Point distances. After some thought, we abandoned that and learnt about Dijkstra's algorithm. Then we wrote our own implementation, which in C# on a decent box takes about 2500ms to find the distance (or time) from one point in Southwest England to every other point in the same area. This is absolutely perfect - we can cache the data against each static location and determine the approximate time to reach it from anywhere. If we make the assumption that we don't ever want to consider drivers further than 20 miles away, we're probably looking at a 10ms hit when we come to use it in reality.