We present a lattice Monte Carlo algorithm based on the one originally proposed by Maggs and Rossetto for simulating electrostatic interactions in inhomogeneous dielectric media. The original algorithm is known to produce attractive interactions between particles of the same dielectric constant in the medium of different dielectric constant. We demonstrate that such interactions are spurious, caused by incorrectly biased statistical weight arising from particle motion during the Monte Carlo moves. We propose a simple parallel tempering algorithm that corrects this unphysical bias. The efficacy of our algorithm is tested on a simple binary mixture and on an uncharged polymer in a solvent, and applied to salt-doped polymer solutions.