You'll be glad to hear C# isn't the cause of your problems
I've done similar things in C++, and MapPoint is the one that is sucking cpu - so C# overheards are not relevant.
Two suggestions:
1.) Cache as much as you can. Route finding is the slow link in the chain, as you are probably aware.
2.) Are as-the-crow-flies distances relevant?
Can these be used to prune the more distant routes?
This could be a double improvement - as well as removing some of the route-finding, these longer routes take the most cpu to find!
Richard