I think UE4’s evaluation of the Idles to Starts transition rule is performed before the Stops to Idles transition has completed. Try modifying the Idles to Starts transition rule so that it does this:
Allow Transition if ( (MoveForward != 0) OR (MoveRight != 0) ) AND (NOT Moving).
We want to make sure we have completely left the Stops state. When we leave the Stops state, our notification should set Moving to False and should set MoveForward and MoveRight to 0.