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.