Alot of good advice above just wanted to add a couple of things. Horses are left or right handed like ppl and some are ambidextrous (just like some ppl) and will travel accordingly. I have noticed in the past with some riders that if the rider is, for example, a strong right handed person riding a horse that is strong right sided then the lesser side (in this example the left) is weaker and the travel of both horse and rider is off. One mistake is that such riders tend not to work as much on directions that are not comfortable to them and the horse and the rider inadvertantly is creating a "lopsided" way of going. In a couple of instance the muscles are visualy more developed in the dominant side of the horse.
Gait idiosycrasy: though more common in Arabians can be seen in gaited breeds from time to time. This is when the horse has its own peculiar way of traveling. It shows up when the horse is traveling at liberty also. Does your horse travel the same way when your not riding him/her? THis happens in humans quite often. However I am not convinced that is what your experiencing.
Video would be great.
"The question is not, can they reason? nor, can they talk? but, can they suffer?" Jeremy Bentham