They use an OPS computer program, just like a lot of carriers do on the 747-400's. You enter your landing weight, landing runway and ATIS information and it spits out the stopping distance with various autobrake settings. In the case of the classic, that would be minimum, medium or maximum. If the stopping distance with that autobrake setting is greater than the runway length, then that autobrake setting is grayed out so you can't use it.
In the case of going into Kabul at max landing weight, the minimum setting is usually grayed out, so the crews would have to use medium. What was happening was that crews were often late to go to minimum once they felt they could get it stopped by the end of the runway with the lower deceleration rate that min autobrakes would give (also using max reversing). As a result, they would end up thermaling tires and getting stuck there.
It just seems odd to me that under normal conditions, any amount of braking would result in thermaled tires if the analysis said you can dispatch to that runway. For instance, if you truly were right at the limit on a dry 10,000' runway, F.A.R. 121.195 requires that you get it stopped by the 6,000' mark (60%). I would presume that this is with maximum manual braking as Mutt pointed out. As far as I know, you can outbrake maximum autobrakes (but not RTO), so even a max autobrake setting would actually be something less than max manual braking.
Given the example above with max braking on the 10,000' runway, you should be able to leave the autobrakes on max all the way down to a stop and still not thermal the tires, right? These guys were thermaling tires with autobrakes on medium.
Also, FAR 25.125 requires that "[t]he brakes may not be used so as to cause excessive wear of brakes or tires." I can't imagine that thermaling tires would be acceptable to the regulators but excessive brake or tire wear would not.