Conclusion: to block the Ads in the Mail app, one just needs to block the adbroker domain: adbroker.mp.dse.microsoft.com.
First the mail app complained that my gmail account could not connect. Thus I removed and reconnected my gmail account. Then Ads appeared on top of the mails. Outrageous! A system app was harassing the user with intrusive Ads!
After several days' of suffering and mourning for the good old version of the Mail app, I decided to take it into my hand to make it great again. Using the Fiddler tool to take a peek at the Internet traffic, one sees the obvious offender, that friggn adbroker site. Well, Microsoft is definitely the main culprit. Then I threw that site into my
hosts file, so that the adbroker domain resolves to localhost.
The Ads were gone, at least, for now. I am not very sure what this entails as I sometimes run a web server on localhost. If anything worse happens, I will definitely switch mail client.