I had the AT KO's on my '97 runner - great tire for the first half of their life. Great in the snow, great off road, reasonably quiet, gas mileage was not much different than the stock tires. After the tread got past half way though, they were LOUD on the road. Snow and mud traction also fell off signficantly. These tires did hold up pretty well though, so that balances things out a bit. If I remember right, I got just over 40,000 miles out of a set, and they still had some life left on them when I sold the 4runner. I'm hard on tires, so for me, I was happy to see 40,000+ miles.
I currently have the REVO's on my '02 (not the AT2's, but the old version, I guess the AT 1's?). I am very disappointed in them. They get great write ups and many people love them, but I'm not impressed. They too were great when new, actually better than the BFG's when new...but quickly lost their appeal. I barely have 20,000 miles on them now and they only have 5-6/32nd's left on them, and they are starting to get loud too. They are cupped badly, despite the alignment being maintained regularly. From half tread on down, I have needed 4wd far too often in snow that just isn't deep/bad (I'm the type to not use 4wd very often at all, as I like to countersteer, ha!). I will be lucky to get another 5-6,000 miles out of these tires. Not impressed at all for the money spent. FWIW, gas mileage dropped off slightly with these, maybe 1 mpg, but not enough to really complain. I have the D range tires (8 ply I believe?).
I have a set of michelin ltx ms2's on my wife's '05 4runner. I cannot tell you how impressed I am by these tires, despite them being a less aggressive tire. The siping makes them as good or even better than most AT tires IN THE SNOW AND ICE (they won't cut in the mud), in my opinion. I don't do a lot of off roading anymore...probably putting these on my '02 next. They last forever, gas mileage is as good as you will get too.
By the way, I meticulously maintain all of my vehicles and rotate tires/do alignments regularly....so any abnormal tire wear would not be caused by maintenance issues.