Assuming the keyswitch is connecting battery power to the "wallwart", first thing I'd do is bypass the switch providing the power, and then connect/disconnect the power wire manually and see if it turns on every time that way.
If it does, the switch is the problem (possibly arcing inside at the high voltage, possibly leaving stuff on the contacts preventing good connection, but htat gets wiped off enough to work sometimes).
If it doesn't, work that way any better than before, it could just be unable to reliably start on DC input vs AC. (I have an Xbox PSU that can't start on DC at all even if it's the same voltage as teh AC would be if it were DC)
It is possible, that polarity might matter if it isn't gettting AC, if some of it's circuitry only work on part of the AC cycle. I'm pretty sure that's why my xbox PSU won't work on DC--part of it works on one half the cycle, and the rest works on the other. So neither polarity DC lets it startup.
It's just not a common problem.
It's also possible that the load at startup is too high for it, and it's shutting down on some startups because it's right at the edge. Try switching it on without any load on it, or at least with the headlight(s) turned off. Then turn the load on after the PSU is on, repeatedly, and it'll work fine if this is the problem. If the load is just plain too high it'll shutdown when the load is applied (but not when it isn't).
Paralleling may work, or it may not, depends on how the output stages are designed. Occasionally you find some that only startup if there's no voltage on the output; if tis' already detecting the "right" voltage it might not startup, so if some of the paralleled units don't startup as fast as others, the first one(s) might be all that power up correctly. Most likely paralleling will work ok, but I wouldn't guarantee it.
In general I find that more of the wide range (100vac-230vac / etc) wallwarts work on DC than any other, and work at lower startup voltages (down to around 50VDC often enough, but sometims only 60-70VDC).
Side note: if you can find 14-15VDC output wallwarts (like some NICD/NIMH/SLA-powered device chargers use as a base PSU, not the charger itself), with taht wide-range input, they'll work better to run automotive-type lights and accessories than 12VDC output stuff.
That said, if you don't want to deal with any of that, I have a couple of used Sevcon DC-DC units with automotive level outputs that were for 28s Li-ion type packs, so they won't work with mine. I'll have to check what their input range is, but I'd part with one cheap+shipping (just want to be able to get one that *does* run on my 14s setups).