This paper presents a family of approximate Bayesian methods for joint anomaly detection and linear regression in the presence of non-Gaussian noise. Robust anomaly detection using non-convex sparsity-promoting regularization terms is generally challenging, in particular when additional uncertainty measures about the estimation process are needed, e.g., posterior probabilities of anomaly presence. The problem becomes even more challenging in the presence of non-Gaussian, (e.g., Poisson distributed), additional constraints on the regression coefficients (e.g., positivity) and when the anomalies present complex structures (e.g., structured sparsity). Uncertainty quantification is classically addressed using Bayesian methods. Specifically, Monte Carlo methods are the preferred tools to handle complex models. Unfortunately, such simulation methods suffer from a significant computational cost and are thus not scalable for fast inference in high dimensional problems. In this paper, we thus propose fast alternatives based on Expectation-Propagation (EP) methods, which aim at approximating complex distributions by more tractable models to simplify the inference process. The main problem addressed in this paper is linear regression and (sparse) anomaly detection in the presence of noisy measurements. The aim of this paper is to demonstrate the potential benefits and assess the performance of such EP-based methods. The results obtained illustrate that approximate methods can provide satisfactory results with a reasonable computational cost. It is important to note that the proposed methods are sufficiently generic to be used in other applications involving condition monitoring.