Another thing occurred to me. When I subtracted off ax^(d-r)(x^r-1), effectively I was able to just lower the exponent of the ax^d term by r. I can do this as many times as I want, so long as the exponent stays >= 0. This is basically just a roundabout way of doing modular arithmetic, this time in the exponent, using modulus r. So, you can entirely ignore the whole "subtract off a polynomial" thing in this particular case and just take your exponents mod r.

So, succinctly, to check for equality,
1. Evaluate (x+a)^n using repeating squaring. At each step take coefficients mod n and exponents mod r. The coefficients will be numbers since a will be a number.
2. Reduce x^n+a by taking the exponent mod r and the coefficients (1 and a) mod n (which probably does nothing).
3. Compare polynomials obtained from (1) and (2) by checking if the coefficients are all equal. If so, (x+a)^n = x^n+a [...in Z_n[x]/(x^r-1)...]; otherwise, (x+a)^n != x^n+a.