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?
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.
The simple answer to this is really very simple.
Just because Shaul attacked and killed every person that he was able to find, doesn't preclude the fact that people were able to hide, and survive, or escape and regroup later.
Our own history is testament to this fact.
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).