Q1: A Wikipedia article cited by @bondonk reports when ימח שמו וזכרו is used and says “it can be applied to any abhorrent enemy of the people”. It can also be used “even in cases of personal slight.” So it seems to be a subjective matter of choice.
Extract of the article:
Haman and others[edit] The phrase originates
with Purim[13] and Haman,[14][15] but can be applied to any abhorrent
enemy of the people[16] such as Shabsai Tzvi[17][18] Spain,[19] Joseph
Stalin[20] Russians,[21] Poles[22] Adolf Hitler,[23][24] Adolf
Eichmann,[25] Mengele,[26] or any other Nazi[27][28] Or even in cases
of personal slight, such as of a bullying father,[29] or conversely as
the father of Israel Zangwill of his playwright son.[30] Yisrael Meir
Kagan used the epithet of the man who tried to persuade him to abandon
his studies.[31]
(See the article itself for the references.)
The article mentions its use with Jesus of Nazareth but not Mohammed. In Chabad Talk there are several references to the idea of not saying "yimach shemo" about another Jew (including Jesus of Nazareth).
In Thoughts on the Weekly Parshah by HaRav Eliezer Chrysler, Parshas Re'ei it is clear that Reb Yosef Chayim Sonnenfeld commented that using the epithet Yimach Shmo was not the way to speak about a fellow-Jew even a secular leader. This despite the fact that R. Yosef Chayim fought the secular establishment tooth and nail without respite. He did everything in his power to negate their authority. He commented that
it makes more sense to pray for them to do Teshuvah than to curse them
(as B'ruryah taught her husband [Rebbi Meir] in B'rachos 10a)!
The article continues:
We dare not curse the Resha'im. What we have to do is to pray
fervently that G-d showers them with a spirit of purity and puts into
their hearts the will to do Teshuvah. It is only with regard to
Amalek, he concluded, that the Torah writes "Blot out the memory of
Amalek" (and this incorporates all enemies of Yisrael and their
oppressors, who stem from the root of Amalek), and it is they whom we
hope and pray may be blotted out from the Book of life.
Thus here we have Rabbinic authority for limiting the use of the phrase to Amalek and those like him. The Chofetz Chaim referred to above (Yisrael Meir Kagan) may have differed or regarded someone who did not want him to study as equivalent to Amalek.
Q2: Evil people in history that did not commit physical acts of murder but rather instructed others.
The quoted Wikipedia article as you see above refers to evil people who did not murder.
