I was having the same problem with the AND() breaking the conditional formatting. I just happened to try treating the AND as multiplication, and it works! Remove the AND() function and just multiply your arguments. Excel will treat the booleans as 1 for true and 0 for false. I just tested this formula and it seems to work.
=(INDIRECT(ADDRESS(4,COLUMN()))>=INDIRECT(ADDRESS(ROW(),4)))*(INDIRECT(ADDRESS(4,COLUMN()))<=INDIRECT(ADDRESS(ROW(),5)))