We propose stochastic solutions to the scattering of electromagnetic waves from penetrable randomly rough surfaces using the vector-based finite-element method (FEM). The random nature of the surface requires the computation to be performed on multiple surface instances. We propose a mesh deformation scheme, which allows the use of a single FEM mesh for computing ensemble averaged quantities. This scheme is used to perform Monte Carlo (MC) iterations, which is much faster than the conventional techniques where a different mesh is utilized for each surface instance. This scheme also allows for MC-free formulations of the problem; in the first kind, we expand the solution in a stochastic basis using the concept of generalized polynomial chaos obtaining ensemble averaged quantities. This results in a larger set of equations that need to be solved just once. In the second kind - the stochastic collocation method - we run the deterministic solver at certain specified points in the random domain corresponding to the rough surface description. We compare these results with those obtained by MC iterations, and outline the computational costs and convergence behavior. We find that stochastic methods are ideal for surfaces with large correlation lengths. For other parameters, the MC approach is preferable. © 1963-2012 IEEE.