What value of pullup resistor are you using?
Perhaps you could try using a lower value resistor? Or if you have a long cable, try using a lower capacitance cable.
I guess 11uS margin (15uS - 26uS) is little much for the safety of reading this chips.
Did you test at the temperature extremes, or only at room temperature? The wide timing margin is needed to accommodate changes in the timing inside the 1-wire chips, which lack accurate clocks and can change substantially over temperature. They can also change from batch to batch.
Ignoring the the 15 us maximum would not be a good practice. While it worked with the 4 devices you tested, at whatever temperature you tested, going beyond the spec is just asking for trouble.
My guess is your pullup resistor is a bit weak. Using a stronger (lower value) resistor will likely pull the line up faster, enabling you to use the DS18B20 timing.