Accurate orbital information might not be necessary or possible, if you can perform broad scanning that can quickly lock in your given target, but it certainly doesn't hurt. The issue is that even having an orbital track, because of the sats being so low in LEO, atmospheric drag will change your orbit rapidly enough that this information can get out of date quite fast.
Convenient and reliable fallbacks I feel are largely a solved problem for SpaceX. They've built their Starlink bus by reusing a lot of the software from the Falcon 9, Dragon, and Starship programs that already had to handle even greater levels of reliability.
Routing and retransmits are indeed quite a novel area for this kind of service. But the laser link will only be locked on one other peer satellite at any given time, and I don't think they plan on reorienting the sats in order to establish laser comms because of the effect it would have on drag as well as albedo. The former impacts service life per sat, and the latter has been a big rallying cry for Starlink opposition due to the impact it has on astronomy and the visible sky.
So if you likely can't reorient to retransmit, your only options are the peer laser link or the ground transit exit node, either or both of which might not exist, but I feel like you would just ack the packets on each hop to your peer and leave it at that.
http://www.circleid.com/posts/20190906_inter_satellite_laser...
While a major leap, Starlink could potentially service internet backbone traffic at substantially lower latencies in such a world.
You can control the overhead while increasing recovery rate over multiple paths fairly well, with non-integer overhead (>1x but <2x, etc) with erasure coding techniques. Some erasure codes can allow you to control that overhead (code rate) precisely, but have legal imbroglios: https://en.m.wikipedia.org/wiki/Fountain_code
Having said that, I don't think this situation will apply to spacex. They probably won't get random bursts of errors. Noise levels will be very deterministic and can be calculated ahead of time by looking at what stars are "behind" the satellite.
The telemetry and tracking itself for the laser links. All the satellites need fairly accurate orbital information from all other satellites; there will be several thousand satellites capable of performing autonomous orbital adjustments to avoid debris and for their own station keeping. There has to be a convenient and reliable fallback for automatically syncing satellites with the rest of the network after a reboot or loss of communication.
The packet network needs to maintain an efficient routing table and provide low packet loss to end-users. My guess is that the only practical choice will be establishing a large number of point-to-point channels with their own retry/error-correction management. TCP/IP isn't capable of dealing with more than about 1% packet loss and I doubt raw optical/wireless links will be reliable enough especially with topology changes, requiring extensive store-and-forward hardware to buffer transmissions waiting for a reliable route or de-duplicating multicast packets at the receiving end. Reassembly and de-duplication on receipt is theoretically feasible; if a tight reception window can be maintained then specialized hardware could filter duplicates sent over 2 or 3 redundant routes to a local receiver without increasing observed latency or using unreasonable amounts of RAM. A combination approach could allow a tradeoff between using double or triple the raw bandwidth but providing low-latency reliability vs. higher latency with retries while maximizing throughput depending on the current network load. It could also be hardcoded for different traffic classes.
I'm not involved in this problem space in any technical capacity but it sounds like a very fun set of problems to solve.