But your last sentence is only true among single-variable polynomials, isn't it? For example, f(x,y)=xy and g(x,y)=x^2 agree on infinitely many points.
Pick one value for x, now you have a single variable polynomial. Verify that it is equal with above mentioned technique.
Pick another value for x, do the same.
Pick a third...
I didn't prove this works, but I think it should. It is however exponential in the number of variables which may be seen as a downside.
Edit:
This can be proven by induction. Let V = (y, z, ...). Then the polynomial can be expressed as
p = (x-x2)(x-x3)f(V) + (x-x1)(x-3)g(V) + (x-x1)(x-x2)h(V), where x1, x2, x3 are the values we test for x. By inductive hypothesis we can prove each of f, g and h to be zero by testing. But if those are all zero then p is zero.
It seems to me that expanding everything to sum-of-products form and checking for equality directly would be simpler than your algorithm and would run about as fast.
