+1 on checking battery terminals AND the other end of the cables, and on the starter, for corrosion, wouldn't be a bad idea after cleaning the terminals & cables, to use dielectric grease. If the terminals are well isolated, use conductive dielectric grease
your description sure sounds like low amperage passing thru to the starter even though the voltage is good