Prove 2+2=2*2 (and similar)
Perl, 166 + 1 bytes
Run with -p (1 byte penalty).
$r='\((S*)';(@b,@a)=@a;push@a,$_ while+s/\+S/S+/||s/$r\+\)/$1/||s/$r\*\)//||s/$r\*S(S*)/(($1*$2)+$1/||s/$r\)/$1/;$\.=/[^S]./s;$_=$b[-1]eq$a[-1]?join'',@b,reverse@a:&quot;&quot;

More readable:

                           # implicit: read a line of input into $_
                           # we leave the newline on
$r = '\((S*)';             # we use this regex fragment a lot, factor it out
(@b, @a) = @a;             # set @b to @a, @a to empty
push @a, $_ while          # each time round the loop, append $_ to @a
+s/\+S/S+/||               # rule 2: change "+S" to "S+"
s/$r\+\)/$1/||             # rule 1: change "(X+0)" to "X"
s/$r\*\)//||               # rule 3: change "(X*0)" to ""
s/$r\*S(S*)/(($1*$2)+$1/|| # rule 4: change "(X*Y" to "((X*Y)+X"
s/$r\)/$1/;                # rule 5: change "(X) to "X"
$\.=/[^S]./s;              # append a 1 to the newline character if we
                           # see any non-S followed by anything
$_=$b[-1]eq$a[-1]?         # if @b and @a end the same way
  join'',@b,reverse@a      # then $_ becomes @b followed by (@a backwards)
  :""                      # otherwise empty $_
                           # implicit: output $_

The input format expresses numbers in unary as strings of S, and requires the two inputs on separate lines (each followed by a newline, and an EOF after both are seen). I interpreted the question as requiring that parentheses should be literally ( ) and addition/multiplication should be literally + *; I can save a few bytes through less escaping if I'm allowed to make different choices.
The algorithm actually compares the first line of input with an empty line, the second with the first, the third with the second, and so on. This fulfils the requirements of the question. Here's an example run:
My input:

(SS+SS)
(SS*SS)

Program output:

(SSS+S)
(SSSS+)
SSSS
SSSS
(SSSS+)
((SS+)SS+)
(((SS*)SS+)SS+)
(((SS*)S+S)SS+)
(((SS*)+SS)SS+)
((SS*S)SS+)
((SS*S)S+S)
((SS*S)+SS)

The duplicated SSSS in the middle is annoying but I decided it didn't violate the specification, and it's fewer bytes to leave it in.
On invalid input, I append 1 to the newline character, so you get stray 1s sprinkled in at the end of the output.