It could be that the story you were told as a child was just that, a story for kids so they wouldn't worry too much about the horses being drowned.

Unfortunately, our sources tell us differently. We read in the Song of Moses, "Horse and driver He has hurled into the sea." (Ex. 15:1) So it seems the horses were drowned.

The commentators were indeed worried about this, was it just? And they bring the explanation in Midrash Mekhilta that it was just: When horse and rider were brought before Hashem for their final judgment, He asked the horse, Why did you pursue my children? and the horse replied, the rider made me do it against my will. And when Hashem asked the Egyptian charioteers the same question, they responded, "the horses forced us against our will." And so both deserved their judgment of drowning.