I've certainly heard both used. And as you say, Google says the same thing. Why would you suppose, given the latter, that they are not both used? As for "validity" - who decides that, on what basis, if not on the basis of usage?
FWIW - hit and miss is not illogical.
Hit and miss refers to multiple tries.
Hit or miss refers to a single try.
Shooting darts at a target is hit and miss, in the sense that if you shoot many then you will likely get both hits and misses. For any given dart, it is a hit-or-miss matter.
Both are current usage, although "hit-or-miss" would sound more logical to my ears.
hit and miss/hit or miss - (adjective, hyphenated if used before a noun.) - carelessly; aimlessly; without plan or direction. If you describe something as hit and miss or hit or miss, you mean that it is done without proper planning or skill, so that its quality varies.
Examples from the web:
- The company still relies on hit-and-miss techniques that seem antiquated by today's standards.
- The tour around the region felt a bit hit and miss, with no clear agenda or plan.
- There was no planning. It was just hit and miss. We handed out the free tickets hit or miss. Some people got one. Others got five or six.
- The service you get in these big stores can be hit-or-miss, depending on the salesperson you talk to.
- An example of hit or miss is finding items on sale at a store you like to go to that has no predictable sale schedule. Sometimes they will be on sale and sometimes they won't be, so visiting the store is hit or miss.