I think you may be barking up the wrong tree, as if the new battery acts low now but it did start after a lot or 12 tries. If a battery is low it will not come back from the dead so to speak. So after many tries a ground or short probably changed enough to allow contact. You may have a short or loose wire, hot or ground, incontenious type conduction that comes and goes. It could even be a ECM type problem, and there is a slight chance it could be remote start related problem but I wouldn't go there just yet. Unless it is a aftermarket system, then I would come off in a new York second, as a lot of these or junk, or more likely installe improperly. I would look at starter now, and maybe replace it as you may have a bad silinoide and it contacts may be bad, or a dead spot in the armature which can cause these systems. Next time this happens, smack the starter and silinoide with a hammer, and she may fire right up. If not get a bigger hammer! If this works just put on a new starter.