The important idea here is that an "ideal" string does not stretch; its length stays constant. Therefore, the distance between the two objects attached to the string, as measured along the length of the string, is fixed. In some sense, the string is acting like the rigid object you mention since the "along the string length" remains the same.
So, in your case, if the hanging mass moves downward by, say, 3 cm, then the cart must also move horizontally by 3 cm. If they didn't move the same amount, then the string would be stretching or it would become loose. Now, since the displacements of the two objects (in their respective directions) must be the same in any given time interval, the velocities must be the same (just divide by a short time interval and take it to zero). Likewise, the accelerations must be the same as well since the velocities are the same.
I'm being a bit sloppy here with directionality and vectors, but I hope my point gets across.
In your original question, you argue that intuitively it doesn't make sense if you examine Newton's second law. It seems you are implicitly assuming that the net forces on the two objects are the same in order to say that the accelerations could be different. This isn't the case (unless they happen to have the same mass). In fact, their accelerations must be the same for the reason stated above.