In this paper, we solve explicitly the optimal stopping problem with random discounting and an additive functional as cost of observations for a regular linear diffusion. We also extend the results to the class of one-sided regular Feller processes. This generalizes the result of Beibel and Lerche and Paulsen. Our approach relies on a combination of techniques borrowed from potential theory and stochastic calculus. We illustrate our results by detailing some new examples ranging from linear diffusions to Markov processes of the spectrally negative type.