Речь идет о лексической избыточности (т. е. понятно, что Тула - это город, а май - это месяц, а значит слова месяц и город лишние). В отличие от тавтологии (масло масляное), которая является ошибкой, лексическая избыточность (плеонастичность) возможна в определенных ситуациях (Ваши примеры - из канцелярской, деловой речи).
Такие сочетания, безусловно, лексически избыточны, однако они получили настолько широкое распространение в современной речи (особенно канцелярской), что уже не считаются ошибочными. Впрочем, если стремиться к безупречности своей речи, слово месяце лучше опускать.
Правильно: в мае, в мае месяце (без дефиса).