I have used Gai a few times in practice mode (but not lately - I need to start playing KoF XI again though, but just haven't gotten around to it). I managed to pull off all his moves eventually, it's just that I'm not confident I could use him during an actual battle. I'm sure he could be great in the hands of some, but I'm one of those people who have been playing fighting games for years and still kind of stink at them (although I love them).
Oh, and he has some move (can't remember if it was a Leader move, or just a regular super move or what) that makes it so Gai or the opponent can't tag out. It's a "fight until one loses" thing (at least that's what I read on an FAQ, I never really tried to switch out after using it).
The one move of his that I really had problems with was this:
qcf, qcf + K, (he rushes toward opponent) then -
forward, forward, back, downforward, up, forward, down, forward
then can finish with either up, back, or down
My problem is the "downforward" diagonol. It messes me up the majority of the time.
Oh, and speaking of Gai, I read that he was based off Baki from Baki the Grappler, which seems pretty cool. Not sure if it's true though, but SNK does like to pay tribute to manga/anime characters like that (Benimaru/Polnareff, Duo Lon/Vampire Hunter D (supposedely), K9999/Tetsuo, etc.).
As for favorite official team, I guess I'd say:
The Ikari Team when it was either Ralph, Clark, and Heidern, or Ralph, Clark, and Leona (and when Leona was kind of cheap in her early appearances).
And I liked the Old Man team from '98 as well. Heidern and Saisyu are two of my favorites. And the Outlaw Team definitely was great (in fact, I used to hope for a team with Eiji, Yamazaki, and Billy - and although it was Gato instead of Eiji, that was fine with me, because I used Gato a lot in MotW).
I also liked the Mr. Big, Geese, Krauser team from '96.
If theres one guy I want to return, it's Lin. I was pretty good with him. Duo Lon is a pretty cool replacement, but I still liked Lin.