After configuring a new Raspberry Pi Zero W, I have not been able to ssh into it over WiFi.

This was still happening after I created the empty file ssh in the boot partition (to enable ssh), and creating wpa_supplicant.conf in the boot partition (to configure WiFi to connect to my wireless router), and verifying the Pi is assigned a guest IP address over DHCP.

I read somewhere that somehow the server-side ssh server keys (host keys) can get botched in some Raspian distros, but the solutions I've seen suggest configuring things from the Raspian desktop which isn't an option for headless pi. Or using dpkg to reconfigure ssh on the Raspian system, but since I can't log in, that's not an option either.

What can I do?