It does kinda sound like the Shimano pedals are defective. Just out of curiosity, what color are the cleats?

Look makes a great light-action spring pedal that's easier to get out of than their regular pedals.

And you should always keep an extra pair of cleats around regardless of what pedals you ride.