We investigate the structure of the quantum S-matrix for perturbative excitations of the Pohlmeyer reduced version of the AdS_5 x S^5 superstring following arXiv:0912.2958. The reduced theory is a fermionic extension of a gauged WZW model with an integrable potential. We use as an input the result of the one-loop perturbative scattering amplitude computation and an analogy with simpler reduced AdS_n x S^n theories with n=2,3. The n=2 theory is equivalent to the N=2 2-d supersymmetric sine-Gordon model for which the exact quantum S-matrix is known. In the n=3 case the one-loop perturbative S-matrix, improved by a contribution of a local counterterm, satisfies the group factorization property and the Yang-Baxter equation, and reveals the existence of a novel quantum-deformed 2-d supersymmetry which is not manifest in the action. The one-loop perturbative S-matrix of the reduced AdS_5 x S^5 theory has the group factorisation property but does not satisfy the Yang-Baxter equation suggesting some subtlety with the realisation of quantum integrability. As a possible resolution, we propose that the S-matrix of this theory may be identified with the quantum-deformed [psu(2|2)]^2 x R^2 symmetric R-matrix constructed in arXiv:1002.1097. We conjecture the exact all-order form of this S-matrix and discuss its possible relation to the perturbative S-matrix defined by the path integral. As in the AdS_3 x S^3 case the symmetry of the S-matrix may be interpreted as an extended quantum-deformed 2-d supersymmetry.