As an English teacher, I say you make a fine point here. I sure see what you are saying. As a native English speaker, I must say I have heard this so much, it sods perfectly fine. This is way to common for me to have an issue. It actually sounds correct whether it adds up or not. I guess I could say "As long as I can remember, we would do this all the time."
Here is what you will notice about each time you here this... It is not a specific point in time. You do not say "I would do this in February of the year 1989." But you may hear someone say "I would do this each February". (or an even less specific time.)