I'm sure teams like the XCats & Buzz could answer better, but I remember working on chairmans submissions back in 97 & 98. At that time, I believe the submission was mostly video based, and I think we had to submit a 5 minute video, and possibly some sort of short writeup to accompany it (nothing like the current essay). I remember throwing our video together in my friend's basement! There were no formal interviews in those two years, though I do believe the judges would come do "interviews" in the pits much like they do now for the other awards. They did not have to go to every team, though much like now, I don't think you ever knew exactly who the Chairman's judges were vs. the other judges.
My recollection from at least 97-00, was that each year the championship event gave out one Championship Chairmans award and I believe 3 honorable mentions (it may have been 5). I want to say Buzz won 5 HM before finally winning Championship Chairmans... or something like that
If I recall correctly, there was no concept of a Regional Chairman's award, it was only submitted at Championships.