Add CAPTCHA verification for received messages and whitelists and blacklists
When a new person sends you an email, send them a CAPTCHA verification to verify they are a human and not a robot. Have whitelists for people who pass the CAPTCHA and blacklists to block human spammers.
Colin Arnott commented
I understand your concerns however as a user of tor, CAPTCHAs are the bane of my existence and I would rather such measures not be implemented on tutanota.
See SpamArrest.com or Gafana.com or Boxbe.com for examples.