The issue, as you said, is that shaking hands between women and non-mahram men is an evil act which the texts indicate is haraam. The Prophet (peace and blessings of Allaah be upon him) said: “For one of you to be stabbed in the head with an iron needle is better for him than touching a woman who is not permissible for him.” Narrated by al-Tabaraani and classed as saheeh by al-Albaani in Saheeh al-Jaami’, hadeeth no. 5045.
In Saheeh Muslim (1866) it is narrated from ‘Urwah that ‘Aa’ishah told him about the women’s swearing allegiance to the Prophet (peace and blessings of Allaah be upon him), and she said: The hand of the Messenger of Allaah (S) never touched the hand of a woman. When he had accepted a woman’s oath of allegiance he said: “Go, for I have accepted your oath of allegiance.”
Evil actions should be changed by any accountable person who sees them and is able to do something about it. The Prophet (peace and blessings of Allaah be upon him) said: “Whoever among you sees an evil action, then let him change it with his hand [by taking action]; if he cannot, then with his tongue [by speaking out]; and if he cannot, then with his heart – and that is the weakest of faith.” Narrated by Muslim (70) from Abu Sa’eed.
Al-Nawawi (may Allaah have mercy on him) said in Sharh Saheeh Muslim: The words of the Prophet (peace and blessings of Allaah be upon him), “let him change it” mean that this is obligatory according to the consensus of the ummah, and there is overwhelming evidence from the Qur’aan and Sunnah and scholarly consensus that it is obligatory to enjoin what is good and forbid what is evil, and it also comes under the heading of naseehah (sincerity or sincere advice) which is Islam. End quote.
Al-‘Allaamah al-Quraafi (may Allaah have mercy on him) said in al-Furooq (4/257): The scholars said that enjoining what is good and forbidding what is evil is obligatory and should be done immediately, according to consensus, and whoever is able to enjoin what is good should do so immediately. End quote.
Al-Nawawi (may Allaah have mercy on him) said in Sharh Saheeh Muslim, describing who is obliged to forbid evil:
Moreover, enjoining what is good and forbidding what is evil is a communal obligation; if some people do it, the rest are absolved of blame, but if all of them fail to do it, then each one who was able to do it but did not, with no excuse or fear, is guilty of sin. And it may become an individual obligation, such as if a person is in a place where no one knows of it but him, or if no one is able to remove it but him, such as one who sees his wife, child or slave committing an evil action or falling short in a good action. The scholars (may Allaah be pleased with them) said: Enjoining what is good and forbidding what is evil is not waived in the case of one who is accountable because he thinks that it will do no good; rather he must do it for the reminder will benefit the believers. End quote.
So denouncing evil is not limited to a certain number of times; rather the one who sees an evil action and is able to denounce it must do so.
But the scholars differed concerning the issue of denouncing evil in the case where one thinks that denouncing it will not deter the person from doing it. Some of them were of the view that denouncing him is obligatory so as to discharge his duty towards Allaah and in the hope that the one who is addressed may benefit from the exhortation. This is the apparent meaning of the words of al-Nawawi quoted above. And some of them were of the view that it is not obligatory but it is mustahabb (recommended) in that case.
Al-‘Allaamah al-Safaareeni al-Hanbali (may Allaah have mercy on him) said in Ghidha’ al-Albaab fi Sharh Manzoomat al-Adaab (1/215): al-Haafiz Ibn Rajab said in his commentary on al-Arba’een al-Nawawiyyah: al-Qaadi Abu Ya’la narrated two reports from Imam Ahmad concerning the issue of whether it is obligatory to denounce an evil action when one knows that the person will not accept that, and he regarded as correct the views that it is obligatory. This is also the view of most scholars. One of the salaf was asked about this and he said: This will be discharging his duty towards Allaah. End quote.
Thus it is clear that if you are able to forbid this evil action, without that leading to a greater evil, such as if the one whom you denounce will become stubborn and will clearly state that he regarded something haraam as being permissible, or he will say bad things about sharee’ah and its rulings, and other such evils which may result from denouncing the evil action, especially if the person who does it is harsh, or he embarrasses him in front of others – if you are able to do it, then it is obligatory for you to denounce this evil action even if you think that they will never stop it, but you should deal as kindly as possible with the one whom you are rebuking, in the hope that this may cause him to accept the advice.
As to whether you should denounce this evil publicly or privately, the basic principle is that the one who does the evil action openly should be denounced publicly, but if someone does it secretly, it is not permissible to rebuke him publicly. Shaykh al-Islam Ibn Taymiyah (may Allaah have mercy on him) said in al-Fataawa al-Kubra (3/434): If a man commits evil actions openly, he must be rebuked openly, and speaking about him in his absence is no longer haraam. End quote.
But in fact the issue of whether it should be done publicly or privately depends on the interest which one hopes to achieve thereby. If one thinks it most likely that the person will benefit from being advised privately, and that he will become stubborn if it is done publicly, then you must advise him privately and deal with him gently. Each case must be dealt with on its own merits.
Finally, we would like to remind you of the reward of Allaah for the one who takes on the mission of calling people to goodness and reminds them of it.
The Prophet (peace and blessings of Allaah be upon him) said: “Allaah, His angels, and the inhabitants of heaven and earth, even the ant in its hole and even the fish, send blessings – i.e., pray for good – upon the one who teaches the people good.” Narrated by al-Tirmidhi (2609) and classed as saheeh by al-Albaani in Saheeh al-Jaami’ hadeeth no 1839.
May Allaah help us all to do that which He loves and which pleases Him.
And Allaah knows best.