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��?