There's a difference between being in SOLDIER and being a soldier. SOLDIER is Shinra's elite, the best of the best. Like Zack and Sephiroth. Cloud never made it into SOLDIER, but he became a soldier in Shinra's regular army.