This could be because how the OSM XML is formated. The nodes are ordered by id not by latitude or longitude and the id don't go in a complete sequence, so they cant be used as a list index. The nodes also have no info about which ways they are part of. Ways on the other hand have have just a sequence of node ids.
There is also a lot of irrelevant information like usernames and timestamps.
I think that with this structure, all operations needed for routing, like computing distance between nodes or finding which way is a node part of would be very, very slow.
My guess is, that in the binary formats:they sort the nodes and ways, so that near nodes/ways can be quickly found nodes have info about which ways they are part of ways have complete info about their nodes every item has some global id, so you can just jump on a position in the file to get relevant data all unneeded items are removed
Also, country sized extracts seem to have 100MB+, for example the whole UK has 218MB.
If I understand this correctly:find nearest node that is a part of a route follow the route in both directions on both ends, choose the node, that is closest to the destination then this for all ways joining the segment between the chosen node and closest one do this for say, 10 steps maximum automatically update as the current position changes Well, this could theoretically get you to in the direction to your destination, by any means possible. At least, it could be quite an adventure.
There also seems to be a binary OSM API for mobile devices, that accepts bounding box input and also supports diffs.