It's giving the sizes of the thumbnails, not size/10. All the 4:3 images in that screenshot are "128x96" which is what the thumbnail sizes would be. I don't see how this could possibly happen, unless something else is thumbnailing the images, and setting the metadata incorrectly in the thumbnails.

Does the problem continue to manifest if you rm -rf ~/.thumbnails and run gnome-background-properties without anything else generating the thumbnails first?

It does the same after removing the thumbnails cache, downgrading GTK to 2.10.7 doesn't make a difference neither

I doubt GTK+ would make a difference. The thumbnailer code is in libgnomeui, not GTK+. The following bit of code looks suspect to me, in libgnomeui:

=================================================
  /* Fall back to gdk-pixbuf */
  if (pixbuf == NULL)
    {
#ifdef HAVE_LIBJPEG
      if (strcmp (mime_type, "image/jpeg") == 0)
	pixbuf = _gnome_thumbnail_load_scaled_jpeg (uri, size, size);
      else
#endif
	pixbuf = gnome_gdk_pixbuf_new_from_uri_at_scale (uri, size, size, TRUE);
    }
      
  if (pixbuf == NULL)
    return NULL;

  width = gdk_pixbuf_get_width (pixbuf);
  g_object_set_data_full (G_OBJECT (pixbuf), "gnome-thumbnail-width",
			  g_strdup_printf ("%d", width), g_free);
  height = gdk_pixbuf_get_height (pixbuf);
  g_object_set_data_full (G_OBJECT (pixbuf), "gnome-thumbnail-height",
			  g_strdup_printf ("%d", height), g_free);
=================================================

According to this, it is setting the thumbnail metadata to the size of the loaded pixbuf, which would be the size of the thumbnail (size is 128, or 256 for large thumbs). Perhaps this code needs to be fixed to get the info on the original uri, rather than the loaded image which is at a smaller size. I would expect to see this same issue in GNOME 2.16 though, as the log entry claims this code was committed in Jan 2006.

Turns out this is a known problem...

*** This bug has been marked as a duplicate of 356930 ***