Your answer got right to the core of the issue. I searched for \r and got matches in exactly those lines which resisted the replacement. What exactly is this \r character, anyway?
I have no idea how that \r entered my fully Linux-based and Linux-generated file.