It would help if you attached a sample of the sheet (with no confidential information)
Conditional formatting does have its challenges and the first is often understanding how it works.
You say: "Sometimes it appears to reference cells that are not in the formula."
and depending on the formula it WILL do this BY DESIGN. So if the 'Applied To' range is A1:D100 then the formula is applied to A1 and then "shifted" to each other cell modifying the cell references the same way formulas are changed when you copy or fill. So anything withOUT a '$' in front of it will shift and thing WITH a '$' will stay the same. SO if you want to highlight any of those rows if the value in column E is >100 then you could use the formula =$E1>100
That means for cell A1 (the top left corner of the Applied To range) will check if E1>100 and as it goes to B1,C1,D1 it will continue to check E1>100 because the $ before the E 'locks' the column E. But as it check A2, A3, A4, etc... it will check E2, E3, E4, etc... because there is NO $ before the '1'.
You say: "Other times the formula is true, but the formatting doesn't change."
but if the formatting doesn't change how do you KNOW the formula is true?
Another thing to check is that Excel tries to be smart about formatting rules and when you insert, delete or move cells, rows, columns it changes the Applies To range and copies the rule as it thinks best (which admittedly is often not what I think is best) and if you change or it THINKS you changed the Applies To range it will also adjust the formula references and sometimes really gets it wrong. There are many cases after I create or fix a rule that I have to go back in and fix the cell references, so double check that also.
Hope that helps but if you attach a sample we could help more.