We sometimes add it to ease the pronunciation. There are some rules but I think it's rather pointless to elaborate on them now. It's pretty easy to pick up as you learn, IMO.
If you're really, really interested in several paragraphs long detailled posts on Czech phonology, just let me know. :D
Isn't mě the only word beze is used with in Czech? It's like that in Polish, bez with everything, but beze mnie. Actually, if you had asked me yesterday when we use beze, I probably would have answered exactly as you did, citing "some rules". It's the first time I've realised we use such forms (nad-nade, pod-pode, od-ode etc.) just for mnie.