What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?
Here's a quick argument for why it works over rings. Given matrices $A$, $B$, $C$, we verify $A B = C$ by picking a random bit vector $v$, then checking if $ABv = Cv$. This clearly passes if $AB = C$. 

Suppose $AB \neq C$ and $ABv = Cv$. Let $D = AB - C$. $D$ is a nonzero matrix for which $Dv = 0$. What's the probability that this occurs? Let $D[i&#39;,j&#39;]$ be a nonzero entry. By assumption, $\sum_{j} D[i&#39;,j] v[j] = 0$. With probability $1/2$, $v[j&#39;] = 1$, so we have 

$D[i&#39;,j&#39;] + \sum_{j\neq j&#39;} D[i&#39;,j] v[j] = 0$.

Any ring under its addition operation is an additive group, so there is a unique inverse of $D[i&#39;,j&#39;]$, i.e., $-D[i&#39;,j&#39;]$. Now, the probability of the bad event $-D[i&#39;,j&#39;] = \sum_{j\neq j&#39;} D[i&#39;,j] v[j]$ is at most $1/2$. (One way to see this is the "principle of deferred decisions": in order for the sum to equal $-D[i&#39;,j&#39;]$, at least one other $D[i&#39;,j]$ must be nonzero. So consider the $v[j]$'s corresponding to these other nonzero entries. Even if we set all of these $v[j]$'s except for one of them  optimally, there is still equal probability for the last one being $0$ or $1$, but still only one of these values could make the final sum equal to $-D[i&#39;,j&#39;]$.)
So with probability at least $1/4$, we successfully find that $Dv \neq 0$, when $D$ is nonzero. (Note $v[j]$ and $v[j&#39;]$ are independently chosen for $j \neq j&#39;$.)

As you see, the above argument depends on subtraction. So it won't work (for example) on arbitrary commutative semirings. Perhaps you could relax the multiplicative properties of the algebraic structure, and still get the result?