Looks like you are using the old v1 routing service. Try the newer service: https://learn.microsoft.com/en-us/rest/api/maps/route?view=rest-maps-2025-01-01
The older service used TomTom data and services directly behind the scenes, and there where the odd location where a route couldn't be calculated.
The newer service uses the same data and backend as Bing Maps (bing.com/maps) which has a lot more data and improved logic.
Note that the API interface and response format of the new version is very different from the v1 service. Also, the new service only accepts post requests. The main reason for this is that there are a lot more options available and it is not possible to use half the options before a GET URL would be too long and cause issues in some system.