1-Wire, DS18B20... How do I search the bus?

The DS18B20 is probably the most common 1-wire device. Here is the datasheet:

http://datasheets.maxim-ic.com/en/ds/DS18B20.pdf

Please look at Figure 16 "Recommended Master Read 1 Timing" on page 17 of 22. The diagram shows the line is supposed to be sampled shortly before 15 us after the initial low pulse began. The timings in the current code are 3 us low pulse, plus 9 us. That's 12 us, which allows the small amount of extra overhead from code execution to be as much as 3 us (if the CPU is running at 8 MHz or slower).

The page you linked suggests 18 us from the initial pulse until sampling (or "A to CR"). That's 3 us beyond the maximum recommended by the DS18B20. Also, your code below generates a 9 us pulse plus a 15 us delay, which is a total of 24 us from "A to CR", or 6 us more than the page you linked, and 9 us more than suggested for the DS18B20. That doesn't seem like such a good approach....

I am open to increasing the timings, but since the DS18B20 and similar chips are so very common, I really think it's a not good to increase the total "A to CR" more than 14 us (it's currently 12), since it's supposed to be less than 15 for those incredibly common parts.

Does it work on your device if you use 4 us pulse and 10 us delay before reading?

Can you capture the actual signal on your device with a digital scope?