I cheat and use the SPDs cleats (and MKS cleats, too) with my eggbeaters, and they seem to work. They aren't as snug as with a SPD pedal, but not overly tight (more loose, really), which I can live with. I suggest you try them out with SPD cleats before you go and buy a pile of new pedals. It would be cheaper to buy an extra pair of shoes if the SPD didn't work.