It seems to me that when I started everybody was "sensei" - but there seems to have been title inflation since then...
OTOH, when speaking to Mitsuteru Ueshiba, who was generally fairly formal, I noticed that he was quite careful about referring to people as "such and such Shihan". Of course, that may be because he's aware of the naming conventions in use now and doesn't want to make waves.
When I first started aikido, in the UK, none of my teachers was ever called 'Sensei'. I regularly heard the term later, however, always applied to K Chiba. The English equivalent of this term was thought to be 'Professor' and I regularly saw letters addressed to 'Prof. K Chiba.'
I do not know when the Hombu practice of titles solidified into the present unwieldy system, but I believe that the instructors who first taught overseas were 派遣師範 (haken shihan) and in the USA they established the 師範会 (shihankai). There might have been some title inflation then, for I am certain that when he first came to the UK, Chiba-shi was not 6th dan, which is the rank commonly recognized here in Japan as equivalent to shihan.
In Hiroshima University all the teachers without exception are called 'Sensei', regardless of whether they are lecturers, associate professors or full professors. There is none of the intellectual contortion involved in trying to attribute a deep meaning to the term, such as 'living/lived before'.