This question reminds me of <a href="http://cstheory.stackexchange.com/questions/16275/natural-candidates-for-the-hierarchy-inside-npi/16279#comment66578_16279">how annoyed I was about an *unexpected* definition of the ring isomorphism problem by Kayal and Saxena</a>:
> Group Isomorphism $\leq_m$ Graph Isomorphism $\leq_m$ Ring Isomorphism. Also Integer Factoring $\leq_m$ Ring Isomorphism [<a href="http://eccc.hpi-web.de/report/2004/109/">Kayal and Saxena</a>]. Also Graph Automorphism $\leq_m$ Graph Isomorphism.

I was annoyed about Integer Factoring $\leq_m$ Ring Isomorphism, because it used a *compressed representation* for rings, and hence used an *unexpected* measure for the length of the input:
> The ring is given by addition/mult tables, but these have a canonical compressed representation for rings (because the additive group is Abelian), so the GI-completeness result for finite structures is not relevant.

However, Emil Jeřábek's comment about isomorphism being in coAM still applies even to this compressed representation (at least if you ignore the part with the base set). We can randomly select a basis, and everything else is uniquely determined from that basis, so the standard IP protocol works. (There are actually many subtleties, even beyond the proof of claim 3.1.2. $RI\in coAM$ given in the paper, but it is true nevertheless.)

<sup>I often learn more from Emil Jeřábek's comments than from the actual answers. He's probably a great teacher, and uses the comments for more interaction with the asker and more focused teaching, than would be possible by a mere static answer.</sup>

Even so testing isomorphism for this example wasn't NP-hard, the can of worms provided by allowing compressed input enables us to come up with actual examples. The paper implicitly assumed that the orders $d_i$ were encoded in binary representation, but why not use unary representation (less compressed) or straight line program representation (more compressed) for the orders?

---

If we allow straight line program representation as a valid compression of the input, then we can easily come up with many NP-hard equivalence test problems similar to the *indexed binary decision diagrams* problem given in the question. Asking whether two boolean formulas (given as straight line programs for the free Boolean ring, using the constants $0$, $1$, the unary minus operation, and the binary addition and multiplication operations) are distinct (non-equivalent) is actually NP-complete (and closely related to SAT). One could call this problem of distinguishing two elements of a free algebra given in straight line program representation the <a href="http://cs.stackexchange.com/questions/55413/what-is-the-name-of-the-word-problem-for-free-groups-under-straight-line-program">*slp distinction problem*</a>. This problem is undecidable for the free modular lattice (on 4 or more generators). But for undecidable problems, it doesn't even matter whether we compressed the input or not, hence some people wrongly believe that it doesn't matter how the input is encoded (if it is only compressed).