How to remove JPEG artifacts in Photoshop?

I stumbled upon a very nice wallpaper, but it's smothered wtih horrible artifacts. I'm pretty adept with PS, but this one has me stumped - how do I remove artifacts? Theoretically it should be simple as the drawing's got a vector-like quality, but even still, brushing over the entire thing seems to be far too much hassle...

I'm using CS2. If anyone can help, it'd be great.

Jam it back in, in the dark.

I'm actually considering doing a completely vector version of it (1600x1200 ftw), but that could take more time and effort than I'm prepared to waste unless someone can link me to a very detailed pen tool tutorial.

As for the clone stamp, I'd rather do something that'd affect the whole photo at once rather than having to get rid of each little artifact individually. Could work, though...

There's nowhere I can't reach.

Originally Posted by evilboris

You cannot remove JPEG artifacts no more then you can improve the quality of a MP3 file. It's a lossy conversion, the lost data cannot be recovered.

In most circumstances, yeah, but I can easily replace what was lost in this instance considering it uses simple colours and shading along with very defined borders/contrasts between the elements in the picture.

Also, there's no such filter present in PS. Shame.

This thing is sticky, and I don't like it. I don't appreciate it.