Always� and �never� can be used with a simple past tense verb, although they are more
often used with verbs in the perfect tenses, the simple present tense or
simple future tense. Here are some examples of the use of these two
adverbs with simple past tense verbs:
�Ellie was always very good at art.� (example in Oxford Advanced Learner�s Dictionary 2005)
�I always thought I�d have children eventually.� (example in online Cambridge Advanced Learner�s Dictionary)
�In those years we always did well against them in one-on-one games.�
(http://sport.guardian.co.uk/smalltalk/story/0,,1926382,00.html)
Personally, I don �t think � �what did people always do in the past�� is
grammatically incorrect, but most of the time people do use ��what did people use to do
in the past��?