Thank you Troberg for your help but I am pretty sure that that will not work. If you look at my code from post#1, the sub BeginPathfinder you will see, the do loop is executed an irregular number of times. I could be blind but I cannot see how to add your code.
Just a bit of futher information, here are some actual timings.
Emulator: Breaks after 5 minutes as it cannot cross a road. This is typical with the emulator, rarely happens on a real device.
Samsung Galaxy Tab 2: 0.255 seconds for 30 iterations to calculate 25 markers between the points in the screenshot (taken from emulator not Samsung, markers not shown).