My approach was to uncompress all compressed images on-the-fly in fit_image_load().
Right, that's essentially what this patch is doing too.
Or I could dig up my patches from October and we'll see how far you get with those?
I think I found your patch: https://lists.denx.de/pipermail/u-boot/2018-October/344673.html
It seems to be doing something very close to what my patch does anyway. My patch goes a little further by also solving the case when no load address is given (in that case it will malloc() a buffer to decompress into with an upper bound guess for the required size). If there is a load size given, the two should end up doing the same thing. Also your patch works on all image types, which as you said there breaks it for kernels. I think the option of doing it for all image types except kernels would be a good solution for everyone. (Ultimately, I think it might be nicer if the kernel decompression would also be handled there and not as a special case, but I'd rather not tackle everything at once. This can always be iterated upon in the future.)