Cleaning Up Poor Quality Images

I have the pleasent job of redesigning a logo for a client. It's a nasty image of a sailboat that was originally a scan off of a business card. The image was about 100 pixels by 100 pixels and I've managed to enlarge it to a decent size to work with, cleaned up all the noise around the image, and cleaned up the background. The problem that I'm a left with is the forground sailboat is really jagged and pixelated. Is there any good method for cleaning up the edges of an image like that.

Here's a sample:

imho you should vectorize it, then stretch it much bigger and clean up the vectors then in illustrator, freehand or even flash. this should give the best results.
the sailboat looks like it´s predetermined to be vectorized

I agree with M.

There's a technique you can do with photoshop that involves blurring the image slightly then using levels or minimize to bring it back into focus. Line intersections get a bit blurred that way, though, and you lose detail. I don't think it would work all that well in this case, but you could try it.