This is easily solved with mDNS/Avahi. I had the same gripe years ago, now my hosts advertise their own records or even on behalf of others without running a NS.