Semi-interpenetrating polymer networks (semi-IPNs) with significant ionic conductivity (10−4 S cm−1 at ambient temperature) were studied by vibrational and impedance spectroscopies coupled with advanced analysis procedures. Vibrational spectroscopy recognized the numbers of free ions, ion pairs, ion–polymers and hydrogen bonds within the solid polymer electrolyte matrices (SPE). Electrochemical impedance spectroscopy (EIS) was used to quantify the bulk resistance and bulk relaxation time. The analyses used discrepancy–complexity plots to assess the number of free parameters properly, and EIS was further analyzed using impedance spectroscopy genetic programming (ISGP). Four compositions of PEO-polyurethane/poly(ethylene glycol) dimethyl ether (PEO-PU/PEGDME) were examined with LiClO4 salt. The polymer electrolyte composition of 30/70 PEO-PU/PEGDME resulted in the lowest relaxation times and the highest ionic conductivity. The best salt concentration was observed at an EO/Li ratio of 30 for the PEO-PU/PEGDME:LiClO4 (30/70) semi-IPN matrix. Several lithium salts of different anions were examined at an EO/Li ratio of 10, and the ionic conductivity achieved varied in the order –N(CF3SO2)2− > –ClO4− > –(CF3SO3)− > –I−/I3−.