If I don't know who my machine is talking to, the information is not very useful. So there needs to be a fallback on some level.

Perhaps there should be a mode where littlesnitch just does its own lookup using the system-configured rDNS, for example from the ui or for specific processes, etc? It should be cached if it is a recent lookup, so minimal performance implications; and offloaded to the system rDNS resolver, so minimal instruction set.