Spots like this are due to something on or very, very near the sensor. See Dust-like speck visible every few pictures — is it dust, or worse? for another example. Dust in or on the lens can't cause this problem, because, like lens scratches, they'll be so far out of focus that the effect is undetectable (in the same way a window screen becomes invisible when focused far away through it).
On an SLR, you can access the glass protecting the sensor, and it's not much of a worry, since you can clean this. And automatic cleaning technology has gotten better. With my first couple of DSLRs, this was a constant annoyance. The first one had no real self-cleaning mechanism, and the second did, but it was ineffectual. With my current camera, which I got in 2009, I've never once had a problem with dust, and I change my lenses a whole lot more than I did five years ago.
With a compact camera, though, the whole thing will need to be disassembled, and this isn't something you can easily do at home — they're not made to be user serviceable. A camera service center will be able to do it, and if they're feeling charitable may in fact clean the sensor under warranty for free. Out of warranty, or if they decide the dust is due to environmental conditions you should have been more careful about, it's generally unreasonably expensive. (I once paid $100 to have a Fujifilm F31fd cleaned in this way.)
So, in this lovely world of disposable consumer gadgets, most people consider this time to get a new camera. If you get a new camera which doesn't have either built-in sensor cleaning or a way to access the sensor for manual cleaning, consider one with environmental sealing (waterproof is also dust-proof).