I tried with the power cable connected to my PC, and I noticed that the error rates were similar on both sensors, and the errors were way less than with the adapter I use, so part of the problem might be coming from the adapter. (Unfortunately I can't test with another power supply, because I don't have another one with 2 amps rating, and I need 2 amps because of a hard drive.)|
Since then I replaced the old telephone cables with CAT5 UTP cables. The lengths are almost the same, about 2 meters to one sensor, and 8 meters to the another. The DATA and GND are twisted together, and I put 100nF capacitors next to both sensors. The pull-up is 2.35k (2x 4.7k in parallel).
The errors are not fully gone, but the error rate is around 1%, that is the best I could achieve so far. The CONVERT_TEMP error still appears in the syslog, but the sensors didn't disappear since then.