Mai stammte aus Üchtelhausen (Kreis Schweinfurt) und spielte bis 1989 beim FC Schweinfurt 05, den er kurz vor dem Zweitliga-Aufstieg unter Werner Lorant Richtung Wattenscheid verließ.
Die SGW war seine erste Profi-Station, für den Lohrheide-Klub machte Mai 77 Bundesliga-Spiele, bis er 1994 zum FC Schalke 04 wechselte, für den er aber nicht zum Einsatz kam. Nach einer weiteren Station bei der SpVgg. Unterhaching beschloss er seine Karriere beim FC Miesbach. Im Sommer 2001 endete seine aktive Zeit als Fußballspieler.