The May you have used is actually the month of May. Should or must would be the preferred options here. Must means it has to be done today while should means there is an option but the preference is that you mail the letters today. I hope this helps.
Caroline