the words "often" and "probably" come up more than they should
But that isn't the datasheet.
the printout says NOT parasite powered
The begin function in the Dallas library searches the bus for devices. For each device that answers it checks to see if the device is parasite powered. If so, it sets a "parasite" flag and then assumes everything is parasite powered after that. It doesn't think your bus is parasite powered.
The problem, I think, is that the resistor you are using is too high a value for parasite mode. Try a 1k5 - that's what I'm using on a bus that has four DS18B20.