What is the best way to solve my unusual lighting and wiring challenge?
You mean single throw switches? 3 way and conventional switches are both single pole, 3 way switches are double throw. As long as the work was done correctly, there is nothing unsafe with using single throw switches even if there are wires for a 3 way setup.

If correctly wired for 3 way, there should be no problem converting to proper 3 way by simply installing 3 way switches. If you want to install lights where none currently exist, you will need to run some wiring, a wireless solution alone will not help since the light fixture has no power at all. You can mount switches where ever and they can communicate wirelessly with the light, but lights need power.

How difficult this would be depends on the specifics of your situation. If you have an accessible attic and the top plate of the wall where the switches are located is accessible as well in the attic, it will not get much easier. Less access means needing to remove finish material for access. Anything in the voids where you fish wires such as insulation or blocking also complicate things.