It would be great to get some pictures illustrating the extent of "loose" (i.e. can you rock the shoe side to side? forward and back?) as well as some close-up photographs of the pedals and cleats. What brand of zero-float cleats are you using? Pedal body wear (and cleat wear) is more critical with zero float cleats, and you may need to replace the pedal body if it is simply a matter of abrasive wear.
Not sure how to add a photo here but i'm using the Garmin Vector compatible cleats in the Garmin branded box. Grey cleat / 0deg float. Cleat is brand new so wear is next to none. I can see that the pedal is worn, specifically on the back from clipping in / out but i've only owned them 3 months so the pedal being that easily worn is annoying. The pedal to the RH side of the photo shows more wear to the corner section. The play is both forward > backward and side to side, easily done by hand. The there is no up and down play though the it's not lifting off the pedal on the upward stroke.