6 degrees of separation is probably the intended design constraint, assuming there are sufficient nodes to do long range propagation it would work, so 3 bits should be enough in theory. Or passive repeaters as you suggest to go even further. But it seems in practice to be insufficient.
Perhaps this is the reason Reticulum works so well? hop limit of 255, support for any transport mechnism so a fragmented internet is still suitable for long range propagation.
Perhaps a per node hash of known recent routes to avoid flooding every single time and using flooding as a backup.