There are two types of SPD cleats.
SH56 multi-release will be easier to get out of and are marketed toward beginners, touring and recreational riders.
SH51 single-release cleat are more secure and only release by rotating the ankle away from the crank arm. These are for aggressive riders and racers.
Is it possible that you have SH56 cleats and are pulling out when you start to pedal because of the way you are moving your feet?
-Tim-