OSMAnd doesn’t always have routing limited to a few hundred kilometers. If one is cycle-touring, then the Brouter engine plugin for OSMAnd can be installed and that generates pretty quickly very long-distance routes.

But with regard to planning long car journeys, there is always the option of generating the route using one of the several OSM-based routing engines on the web, then downloading a GPX file, opening it in OSMAnd, and telling OSMAnd that is the route you want to follow.