Translated, a sensei is someone who has gone before, although who exactly "deserves" to have that title, is going to vary from one system to another.
I've seen some systems automatically grant that title to someone once they hit shodan, but I've also seen other systems only grant that title to someone who actually runs a school.
In our system, "sensei" is reserved for the more senior instructors who are in charge of running classes on a consistent basis, and have proven themselves over the years.
Those who want to become instructors have to pass the sempai examination, and demonstrate that they can effectively teach someone one on one, on a regular basis. Eventually, those sempai who show enough initiative, are given a chance to teach classes on a regular basis.
Once they do this, and then meet a minimum rank requirement, then they are eligible to become sensei, based on the chief instructor's evaluation.
Regardless of the system, though, it never really hurts to call a fellow instructor "sensei" when you meet them. After all, if you are an instructor, then you do fit the meaning of "one who has gone before," and even if you have a title of shihan, renshi, kyoshi, hanshi, etc., you are still sensei to the other sensei as well, so the title is still valid.
