Edit: This post was in response to FDibbins; npamcpp hadn't posted when I hit reply. I will try npamcpp's suggestion now. Thanks.

I think I have tried that already, but just to make sure, I tried it again without success. I started from the document uploaded here, and tried "use formula" with both "=a1<>c1" and "=$a1<>$c1", because I'm not sure which is the "correct" syntax for this application. In both cases the formatting applied correctly initially, but when I deleted the three bad lines, the formatting stayed. I was left with a new rule, with the original rule only applying to lines 1-34, and the new rule applying to lines 34-65536. (Top half of image below)

I did find that if I go in to "Manage Rules," adjust the "Applies to" field back to "=$C:$C" and delete the newly created rule, as in the bottom half of the image below, then everything goes back to the way it's supposed to be. I'm not strong enough on macros to automate this action, sadly, and I can't help thinking that there's something I'm missing here that would make it "just work like it used to."

excel.jpg