Probably this is some kind of lag, and the "randomness" is actually when the game demands the most processing/memory/graphics power... So try lowering your settings.
No, no, that's not it at all. It's hard to explain, but some games, when you let go of the movement key, the character stops on the spot, like immediately, and some games keeps the character moving for a few tenths of a second and gradually come to a stop, like you stop on ice. My New Vegas has both, sometimes the character stops immediately and sometimes like on ice.
This is ruining my game, I can't play it like this.