Replacing the earlier sequential search through the routing table with a binary search has significantly sped up lookups, which can happen up to twice per packet forwarded (once for source address, once for destination address).
With "only" 16 million addresses in AMPRnet, why don't you use a 16-million entry array holding the next hop for each IP in 44.x.x.x or zero for those addresses that have no tunnel? Then you only need a single index operation to get the next hop for a packet. That requires 64MB of memory to store, hardly a significant amount today. And it can double-up as the filter to forward traffic only to/from registered addresses.
Of course the update operation becomes more expensive, but it could probably be done in-place without disrupting packet forwarding. Or you could build a second table and then switch to it after the build is complete (requiring 128MB).
Rob