Similar to this question.
How did Dovid Hamelech kill the Amaleikim when they were almost completely obliterated (their only survivor was a baby fathered by Agag on his last day) by Shaul Hamelech not long beforehand?
Mi Yodeya is a question and answer site for those who base their lives on Jewish law and tradition and anyone interested in learning more. It only takes a minute to sign up.Sign up to join this community
According to Maimonides (Hil. Melachim 6:4), the obligation to kill Amalek only applies to those Amalekite communities that refuse to accept the terms demanded by the Jewish king (including the acceptance of the seven Noahide laws). Those communities that accept these terms are not to be harmed, even Amalekites. (As the Kesef Mishneh puts it, by accepting the seven mitzvos they are no longer in the category of Amalek.)
Unfortunately, nothing prevents these communities from breaking their word when they believe it safe to do so.
According to the Rambam, it is possible that some Amalekites accepted the peace terms offered by Shaul (which he was required to do by halacha) but later broke their word and returned to being Amaleikim.
This answer may not satisfy the rationalists among us.
Rashi Shmuel 1 15:3 writes that the Amalekites were able to transfrom themselves in to animals (the first animagi :-) ), and these were the animals that Shaul did not destroy and eventually they transformed themselves back into people. (from Sefer Mishbetzot Zahav on Shmuel Alpeh pg 257 citing Sefer Si'ach Mordechai)
He also cites Rav Wosner Zt"l (Shevet Halevi Vol 5 Kuntres Hamitzvot) that Shmuel was able to hear human voices from those sheep (based on Shmuel 1 15:14).