Easy to handle, just use the rules of that time — single domain for single IP. Not applicable to v6 and dyndnses, but something like this can solve it.
IMO the .com domain name fees are… acceptable. It’s similar to how we deal with scarce resources in almost every other domain. The only real improvement I can think of would be some sort of LVT-like-system where high-value domains (dictionary words, short domains) would cost more than low-value ones (robertospizzaottawa.com) to discourage camping.