It sounds like you're using the SPD single-release (twist motion) cleats? What about SPD multi-release cleats (model # SH-56)? They allow you to pull your foot out in more directions. You wouldn't have to change your pedals in order to try these new cleats.

I don't really like them because they release too easily IMO, but they might be perfect for your situation.