I love my SPD pedals and mtn bike shoes on my LHT. The tension has been adjusted so that it is extremely easy to clip in/out, I don't even really notice my foot moving much for either. I was a little concerned at first that perhaps it was adjust too lightly and that I would unclip while hill climbing but that has not been a problem.

Have you had someone look at your cleat position and tension?