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.
What we mean by a frictionless pulley is that the friction in the bearings of the pulley is negligible, and the pulley is free to rotate without any resistance. We don't mean that the friction between the string and the pulley surface is negligible. In fact, we assume that there is enough static friction between the string and pulley surface to prevent the string from slipping. But, in this case, if you do a moment balance on the pulley, you must then conclude that the tensions in the string on either side are equal (even if the pulley has angular acceleration), since the moment of inertia of the pulley is assumed to be zero.
Best Answer
Yes, in these types of problems, you assume that the two masses move with the same velocity and acceleration since the string is considered inextensible.