How did the Bat-Signal work on cloudless and moonless nights?
Because the Bat-signal (being a searchlight, or, in the newer iterations, a laser system) works off of light, it technically couldn't be visible without something to diffuse the light (like clouds or smoke) or reflect the light (like a solid surface). When it is visible without clouds (usually in the animated series), it's simply movie magic.
But the Bat-signal wasn't necessary to contact Batman: when the Bat-signal was otherwise unavailable, the Bat-phone was used:
This was obviously updated for later iterations of Batman, as Wikipedia describes:
In the modern Batman comic book continuity, the Batphone made its debut in Detective Comics #786 (November, 2003), in the form of an encrypted cellphone that allowed Gordon to securely contact Batman, as well as allowing other calls just like a normal cellphone. It also carries a tracking device in case of trouble. Unlike the original Batphone, the device is not red and looks like a regular cellphone.