"Could not find installation information for this machine" after disk erase
I resolved this issue by changing the Wi-Fi network I was connected to. I was on xfinitywifi which was requiring a registration I didn't see. As soon as I connected to my internal company Wi-Fi network without a click-through screen it worked.

Other avenues to resolve this are making a bootable installer, booting from recovery or otherwise connecting to a new network if that’s causing the issue (Ethernet instead of WiFi for instance)