The greed removing modifier ? affects where the match ends, not where it starts. It always starts matching as early as possible. You want:

s{<tr (?:(?!<tr).)* NOTWANTED .*? </tr>}{}xgs;
[download]

(?:(?!<tr).)* reads as "0 or more characters which do not match the regex <tr". It is to regex what [^abc]* is to characters.

By the way, I switched from s/// to s{}{} since / is a common characters in HTML. I also removed the m switch since you use neither ^ nor $.