We had a discussion about this topic a few weeks ago (http://www.jsp-develop.de/forum/view/37632/ [in German]) and came to the same conclusion: Either use ImageMagick or scale the image down in small steps.
So at least, you are not alone with this problem ;-)

I was in a similar position not so long ago. I had screeds of Java2D code that was ugly as heck and (thus) awkward to modify when I needed to add in image rotations. JAI saved the day. It performs as quick as, or quicker than Java2D (with or without the native libraries installed), and provides much more sensible image scaling quality. Plus it does it in a matter of 2-3 lines of code, instead of all that Graphics2D nonsense. Any time you put into figuring out JAI is well worth it IMO.

(only downside is that JAI needs a LOT more memory to get its job done - something about tiles/tile caches. I didn't have time to figure it out so just gave my Java process more memory)

from http://java.sun.com/j2se/1.5.0/docs/guide/2d/new_features.html#bi

The 2D implementation now supports bicubic interpolation and uses it whenever requested. Previously, the VALUE_INTERPOLATION_BICUBIC hint defined by the RenderingHints class wasn't honored, and bilinear interpolation was used instead.

were you using 1.5 or 1.4 ?

(@Johnt) I've just ran my test again, now based on JDK 1.5 and helas: same bad results. Thx for the suggestion though...

(@Richard) Sorry for not being clear in my original posting: I _did_ do the effort of getting into JAI and use that, but again, with similar awkward-looking results. (yeah, even on java 1.5 now)

Try the folowing code:

public static void createThumbnail(File original, File resized, int maxSize) throws IOException, RTException
{
Image i = ImageIO.read(original);

Image resizedImage = null;
int iWidth = i.getWidth(null);
int iHeight = i.getHeight(null);
if (iWidth > iHeight)
resizedImage = i.getScaledInstance(maxSize,(maxSize*iHeight)/iWidth,Image.SCALE_SMOOTH);
else
resizedImage = i.getScaledInstance((maxSize*iWidth)/iHeight,maxSize,Image.SCALE_SMOOTH);

// This code ensures that all the
// pixels in the image are loaded.
Image temp = new ImageIcon(resizedImage).getImage();
// Create the buffered image.
BufferedImage bufferedImage = new BufferedImage(temp.getWidth(null), temp.getHeight(null), BufferedImage.TYPE_INT_RGB);
// Copy image to buffered image.
Graphics g = bufferedImage.createGraphics();
// Clear background and paint the image.
g.setColor(Color.white);
g.fillRect(0, 0, temp.getWidth(null),temp.getHeight(null));
g.drawImage(temp, 0, 0, null);
g.dispose();

// soften
float softenFactor = 0.01f;
float[] softenArray = {0, softenFactor, 0, softenFactor, 1-(softenFactor*4), softenFactor, 0, softenFactor, 0};
Kernel kernel = new Kernel(3, 3, softenArray);
ConvolveOp cOp = new ConvolveOp(kernel, ConvolveOp.EDGE_NO_OP, null);
bufferedImage = cOp.filter(bufferedImage, null);

// suffix of resized should always be jpg
String resizedpath = resized.getPath();
if (!resizedpath.endsWith("." + THUMBEXT))
{
resizedpath += "." + THUMBEXT;
resized = new File(resizedpath);
}

// write the jpeg to a file
ImageIO.write(bufferedImage, THUMBEXT, resized);
}