Let me first appologise if my answer is not what you expect, but I'm not a
cadabra developer... so I might be wrong about the internal functionalities of the software.
It seems that the algorithm
substitute search for an expression (like a "string" in programing) and replace it by a new one... without further manipulations.
If the above is right, then in the first of your code blocks:
ex:=-a**2 - b**2 - 2 a b;
the substitution would return
-a**2 + a**2 + 2 a a
which is wrong because the minus sign was not modified by the
**2 (square) operation!
Given the describes behaviour you have to be extra careful in substituting if your expression contains powers.
You could define a function to substitute properly:
def my_subs(ex, rl):
foo := - a**2 - b**2 - 2 a b;
rul := b -> - a;
will return the expected zero.