Stateful apps face difficulties in scaling as users need to continue sending requests to the same system to maintain their state data. Scaling becomes a challenge when the server cannot handle increased client traffic, resulting in delays or system unavailability.