Maybe this is why Rashi (to 25:19) understands זכר in a more concrete sense: it doesn't mean eradicating "their memory" in the abstract, but "anything which is a remembrance of them" - i.e., as he says, any person from that nation or anything that ever belonged to them.
That we'll still remember them annually isn't a contradiction to that. (Incidentally, even if it wasn't an annual obligation, there'd still be the fact that their name is mentioned in the Torah, and anyone who studies it would come across them soon enough.) This is somewhat in the same vein as the halachah that you are allowed to say the name of any pagan deity mentioned in the Torah; the Lubavitcher Rebbe zt"l explained (Likkutei Sichos 23:168ff) that this is because Torah is the very antithesis of idolatry, so mentioning it in that context doesn't imply any respect for it, but on the contrary, ridicule of its worthlessness.
Same here, then: since Torah and Amalek are polar opposites, then if the only place left where there is a memory of Amalek is in the Torah, then any remembrance of its negativity is gone. (Whereas if there was something left over of theirs, it might not evoke positive associations, but it wouldn't stand in opposition to them either.)
Like all Torah commandments, "timche et zecher amalek" has a clear halachic definition. Rashi (Devarim 25:19) tells us what "zecher amalek" means:
"From man unto woman, from infant unto suckling, from ox unto sheep" (translated from Artscroll Rashi)
Similarly, Rambam writes (Hilchot Milachim 1:1)
'ולהכרית זרעו של עמלק שנאמר 'תמחה את זכר עמלק - [Yisrael, when they enter E Israel, are commanded] to destroy the offspring of Amalek as it says "Destroy the memory of Amalek" (my translation).
We see from here that "zecher Amalek", in this context, means the offspring of Amalek, and is not an all-inclusive term for memory of Amalek. We can wipe out their offspring and still remember what they did to us by reading the Torah portion involving the incident we are commanded to remember.
I don't remember the source, but one of the earlier understandings of "wipe out the memory of Amalek" is that it is a euphemism which means that you wipe out the descendants and people. Meaning, if they have no children, they have nobody to remember them. One could tie this to Yizkor as a concept.
I don't like that answer, because the Torah would not need to be so cryptic or use a euphemism here. And I do not believe it uses such a euphemism elsewhere.
On the surface of the text, we are meant to remember what Amalek DID but not necessarily who Amalek were, and so its possible to wipe out the memory of the nation. We know nothing of their culture or life style, and in that way they were forgotten. (Drashot assuming their most evil trait not withstanding) I am not even sure if we know for certain their borders.
The Sefer Zera Yitzchak answers this question beautifully (IMHO). He says since we don't really know who Amalek is nowadays, the only way we can erase their memory is by erasing their philosophy.
What is their philosophy? Rashi writes, on the word "Karecha" - "Lashon Mikreh" a language of "happenstance." According to Amalek everything is a happenstance, and therefore by always erasing from our mind the Yetzer Hara that says "everything is a coincidence" we are erasing the memory of Amalek.
EDIT: Also, Rav Meir Eliyahu Shelit"a says "Zachor WeAl Tishkah" remembering is up to you, but not forgetting is up to Hashem (meaning, you must pray that you don't forget).
R' Samson Raphael Hirsch sees the "זכר" (translated in the question as "memory") that needs to be erased as not simply the memory of the historical fact of Amalek, but the glorification of their values. To explain this commandment to "erase" in Deuteronomy 25:19 R' Hirsch points us to his comment on Exodus 17:14, where God makes a parallel promise to erase the זכר of Amalek, Himself:
It is not Amalek who is so pernicious for the moral future of mankind but זכר עמלק, the glorifying of the memory of Amalek which is the danger. As long as the annals of humanity cover the memory of the heroes of the sword with glory, as long as those that throttle and murder the happiness of mankind are not buried in oblivion, so long will each successive generation look ip in worship to these "great ones" of violence and force, and their memory will awaken the desire to emulate these heroes, and acquire equal glory with equal violence and force.
R' Hirsch understands the Amalekite glorification of violence as so antithetical to the Torah's ideal of humane morality that the obliteration of this glorification is "the final goal of God's management and direction of the history of the world." Given the centrality of this mission, it's not surprising that God exhorts us to "remember" (Deut. 25:17) Amalek's atrocity and "not forget" (:19) our part in the historical mission of obliterating it. In his commentary on 25:19, R' Hirsch says:
Forget this not, when you falter irresolutely and, Amalek-like, do not recognise God, and in big or small matters only seek opportunities to use your superiority in anything to the detriment of your fellow-men.
If you ever forget your calling as Israel and your mission as Israel in the world and feel envious of the laurel wreaths which a deluded world weaves to crown the memory of successful victorious wreckers of human happiness, and forgets the tear-soaked soil out of which the laurel grew for such wreaths.
Forget this not, when you yourself have to suffer under Amalek's coarseness and power. Keep upright! Keep your humaneness and respect for that which is right even as your God has taught you. That is where the future lies, humaneness and justice will remain the victors over brutality and force, and you yourself are sent to proclaim that victory and that future by your fate and example and to be a co-worker in bringing it about.